編寫算法實現在線性表中查找值為x的元素,如果查找成功,返回1;
否則,返回2,並且把x插入到正確的位置,使線性表仍按升序排列。
依次輸出調用查找插入算法後的線性表中的元素。
提示:存儲結構采用代表頭結點的循環單鏈表,結點結構如下:
typedef?struct?Node
{int?data;
struct?Node?*next;}LNode,*LinkList;
要求:(1)編寫函數建立循環單鏈表CreateLinkList(int?n),函數返回值類型為LinkList。
LinkList?CreateLinkList(int?n){
LNode?*head; int?i=0; LNode?*p,*q; head=malloc(sizeof(LNode)); head->next=head; q=head; while(i<n) {scanf("%d",&a);
p=malloc(sizeof(LNode));
p->data=a;
p->next=q->next;
q>next=p;
q=p;
i++;
} return?head;/*按照升序輸入n個整數,建立帶表頭結點的循環單鏈表*/}
(2)?編寫查找函數QueryLinkList(LinkList?*L,int?x)實現查找並插入功能,函數返回值類型int。
int?QueryLinkList(LinkList?L,int?x)
{?/*查找值為x的元素,若查找成功返回1,否則返回0,並把x插入到相應的位置。*/
int?found=1;
LinkList?p,q;
p=L->next;
while(p!=L?&&?p->data!=x)?p=p->next;
if(p==L)
{
found=0;
q=malloc(sizeof(LNode));
q->data=x;
p=L->next;
while(p->data<x?&&?((p->next)->data<x?||?p->next!=L))?p=p->next;
q->next=p->next; p->next=q; } return?found;}
(3)編寫函數Display(LinkList?L),輸出線性表中的元素。
void?Display(LinkList?L)
{
LinkList?p=L->next; while(p!=L){
printf("%d\t",p->data);
p=p->next;
}
printf("\n");
}
(4)main函數調用QueryLinkList()函數,輸出查找結果,然後調用Display函數依次輸出線性表中的元素。Input輸入元素個數n依次輸入n個升序排列的整數輸入帶查找的元素值x
int?main()
{
LinkList?L;
int?n,x;
scanf("%d",&n);
L=CreateLinkList(n);
scanf("%d",x)
n=QueryLinkList(L,x);
print("%d\t",n);
Display(L);
return?0;
}
Output輸出查找結果1或者0依次輸出線性表中的元素值
Sample?Input
sample?1:?6?2?5?8?10?12?1610
sample?2:?62?5?8?10?12?16?9
Sample?Output
sample?1:?1?2?5?8?10?12?16
sample?2:?0?2?5?8?9?10?12?16