鏈表是數(shù)據(jù)結(jié)構(gòu)中一種最基本的數(shù)據(jù)結(jié)構(gòu)，它是用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表。它較順序表而言在插入和刪除時(shí)不必移動(dòng)其后的元素。現(xiàn)在給你一些整數(shù)，然后會(huì)頻繁地插入和刪除其中的某些元素，會(huì)在其中某些時(shí)候讓你查找某個(gè)元素或者輸出當(dāng)前鏈表中所有的元素。

下面給你基本的算法描述：

圖1：鏈表類型的定義以及獲得鏈表元素的算法描述

圖2：鏈表的插入算法描述

圖3：鏈表的刪除算法描述

圖4：鏈表的創(chuàng)建算法描述

輸入

輸入數(shù)據(jù)只有一組，第一行有n+1個(gè)整數(shù)，第一個(gè)整數(shù)是這行余下的整數(shù)數(shù)目n，后面是n個(gè)整數(shù)。這一行整數(shù)是用來初始化列表的，并且輸入的順序與列表中的順序相反，也就是說如果列表中是1、2、3那么輸入的順序是3、2、1。

第二行有一個(gè)整數(shù)m，代表下面還有m行。每行有一個(gè)字符串，字符串是“get”，“insert”，“delete”，“show”中的一種。如果是“get”或者“delete”，則其后跟著一個(gè)整數(shù)a，代表獲得或者刪除第a個(gè)元素；如果是“insert”，則其后跟著兩個(gè)整數(shù)a和e，代表在第a個(gè)位置前面插入e；“show”之后沒有整數(shù)。

輸出

如果獲取成功，則輸出該元素；如果刪除成功則輸出“delete?OK”；如果獲取失敗或者刪除失敗，則輸出“get?fail”以及“delete?fail”。如果插入成功則輸出“insert?OK”，否則輸出“insert?fail”。如果是“show”則輸出列表中的所有元素，如果列表是空的，則輸出“Link?list?is?empty”。注：所有的雙引號(hào)均不輸出。

樣例輸入

3 3 2 121showdelete 1showdelete 2showdelete 1showdelete 2insert 2 5showinsert 1 5showinsert 1 7showinsert 2 5showinsert 3 6showinsert 1 8showget 2

樣例輸出

1 2 3delete OK2 3delete OK2delete OKLink list is emptydelete failinsert failLink list is emptyinsert OK5insert OK7 5insert OK7 5 5insert OK7 5 6 5insert OK8 7 5 6 57



#include<stdio.h> #include<string.h> #include<malloc.h> #define NULL 0struct stu{int num;struct stu *next; }; int N,n; int num3; struct stu *creat(){struct stu *head;struct stu *p1=NULL;struct stu *p2=NULL;n=0;p1=(struct stu *)malloc(sizeof(struct stu));p2=p1;if(p1==NULL)return NULL;else {head =NULL;scanf("%d",&(p1->num));num3=p1->num;}while(n<N){n+=1;if(n==1){head=p1;p2->next=NULL;}else{p2->next=p1;}p2=p1;p1=(struct stu *)malloc(sizeof(struct stu));scanf("%d",&(p1->num));num3=p1->num;}p2->next=NULL;free(p1);p1=NULL;return head; }; struct stu *del(struct stu *head,int num){struct stu *p1;struct stu *p2;if(head==NULL){printf("delete fail\n");return head;}p1=head;n=1;while(n<num&&p1->next!=NULL){p2=p1;p1=p1->next;n++;}if(n==num){if(p1==head){head=p1->next;}else{p2->next=p1->next;}free(p1);p1=NULL;N-=1;printf("delete OK\n");}else{printf("delete fail\n");}return head; }; struct stu *insert(struct stu *head,struct stu *node,int num1){struct stu *p1;n=1;if(head==NULL){if(num1==1){head=node;node->next=NULL;N+=1;printf("insert OK\n");}elseprintf("insert fail\n");return head;}p1=head;if(head!=NULL&&num1==1){node->next=p1;head=node;printf("insert OK\n");return head;}while(n<num1-1&&p1->next!=NULL){n++;p1=p1->next;}if(n==num1-1){node->next=p1->next;p1->next=node;N++;printf("insert OK\n");}else {printf("insert fail\n");}return head; }; struct stu *reverse(struct stu *head){struct stu *p;struct stu *p1;struct stu *p2;p1=NULL;p2=head;while(p2!=NULL){p=p2->next;p2->next=p1;p1=p2;p2=p;}head =p1;return head; }; void print(struct stu *head){struct stu *p;p=head;if(head!=NULL){do{printf("%d",p->num);p=p->next;if(p!=NULL)printf(" ");}while(p!=NULL);printf("\n");}else printf("Link list is empty\n"); } void gt(struct stu *head,int num){struct stu *p;p=head;n=1;while(n<num&&p->next!=NULL){p=p->next;n++;}if(n==num){printf("%d\n",p->num);}elseprintf("get fail\n"); } int main(){struct stu *head;struct stu *stu1;scanf("%d",&N);head=creat();//print(head);head=reverse(head);//print(head);//int num;int i,j;//scanf("%d",&num);//printf("%d\n",num);char s[20];int num1,num2;for(i=0;i<num3;i++){scanf("%s",s);if(strcmp(s,"show")==0){print(head);}else if(strcmp(s,"delete")==0){scanf("%d",&num1);head=del(head,num1);}else if(strcmp(s,"insert")==0){stu1=(struct stu *)malloc(sizeof(struct stu));scanf("%d %d",&num1,&(stu1->num));head=insert(head,stu1,num1);}else if(strcmp(s,"get")==0){scanf("%d",&num1);gt(head,num1);}memset(s,'\0',sizeof(s));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的数据结构，链表基本操作的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。