Problem D: 鏈表的基本運算（線性表）
Time Limit: 1 Sec??Memory Limit: 128 MBSubmit: 18??Solved: 10
Description
編寫一個程序，實現鏈表的各種基本運算（假設順序表的元素類型為char），主函數已給出，請補充每一種方法。
?
1、初始化單鏈表L；
2、采用尾插法依次插入元素a,b,c,d,e；
3、輸出單鏈表L；
4、輸出單鏈表L的長度；
5、判斷單鏈表L是否為空；
6、輸出單鏈表L的第三個元素；
7、輸出元素a的位置；
8、在第四個元素位置插入元素f；
9、輸出單鏈表L；
10、刪除L的第三個元素；
11、輸出單鏈表L；
12、釋放單鏈表L；
????
數據元素類型定義為
typedef char ElemType;
?
順序表的定義為
int main()
{
??? SqList *L;
??? InitList(L);??????????????????????????? //初始化單鏈表
??? ElemType a,b,c,d,e;
??? scanf("%c %c %c %c %c%*c",&a,&b,&c,&d,&e);
??? Insert(L,a);
??? Insert(L,b);
??? Insert(L,c);
??? Insert(L,d);
??? Insert(L,e);??????????????????????????? //使用尾插法插入元素a,b,c,d,e
??? Print(L);?????????????????????????????? //輸出單鏈表
??? PrintLength(L);???????????????????????? //輸出單鏈表長度
??? if(SqNull(L))
??????? printf("單鏈表不為空\n");
??? else printf("單鏈表為空\n");??????????? //判斷單鏈表是否為空
??? PrintData(L,3);???????????????????????? //輸出第三個元素
??? printf("元素a的位置：%d\n",Find(L,a));? //輸出元素a的位置
??? ElemType f;
??? scanf("%c",&f);
??? Insertinto(L,4,f);????????????????????? //將f插入到第四個位置
??? Print(L);?????????????????????????????? //輸出單鏈表
??? Delete(L,3);??????????????????????????? //刪除第三個元素
??? Print(L);?????????????????????????????? //輸出單鏈表
??? free(L);??????????????????????????????? //釋放內存
??? return 0;
}
Input
第一行輸入五個元素a,b,c,d,e；接下來輸入元素f；請根據題目編寫算法。
Output
Sample Input
1 2 3 4 5
6 Sample Output
1 2 3 4 5
5
單鏈表不為空
3
元素a的位置：1
1 2 3 6 4 5
1 2 6 4 5 HINT
請使用C++編譯并提交
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct Node
{ElemType data;struct Node *next;
} SqList;
void InitList(SqList *&L)
{L=(SqList*)malloc(sizeof(SqList));L->next=NULL;
}
void Insert(SqList *&L,ElemType n)
{SqList *p=L,*q;while(p->next!=NULL)p=p->next;q=p;p=(SqList*)malloc(sizeof(SqList));q->next=p;p->data=n;p->next=NULL;
}
void Print(SqList *L)
{SqList *p=L->next;while(p->next!=NULL){printf("%c ",p->data);p=p->next;}printf("%c\n",p->data);
}
void PrintLength(SqList *L)
{int i=0;SqList *p=L->next;while(p!=NULL){i++;p=p->next;}printf("%d\n",i);
}
bool SqNull(SqList *L)
{SqList *p=L->next;if(L->next!=NULL)return true;else return false;
}
void PrintData(SqList *L,int n)
{SqList *p=L->next;int i;for(i=0; i<n-1&&p->next!=NULL; i++)p=p->next;printf("%c\n",p->data);
}
int Find(SqList *L,ElemType a)
{SqList *p=L->next;for(int i=0; p!=NULL; i++)if(p->data==a)return i+1;return 0;
}
void Insertinto(SqList *&L,int n,ElemType f)
{SqList *p=L->next,*q;for(int i=1; p!=NULL; i++){if(i==n-1){q=(SqList*)malloc(sizeof(SqList));q->data=f;q->next=p->next;p->next=q;}p=p->next;}
}
void Delete(SqList *&L,int n)
{SqList *p=L->next,*q;for(int i=1; p!=NULL; i++){if(i==n-1){q=p->next;p->next=p->next->next;free(q);}p=p->next;}
}
int main()
{SqList *L;InitList(L); //初始化單鏈表ElemType a,b,c,d,e;scanf("%c %c %c %c %c%*c",&a,&b,&c,&d,&e);Insert(L,a);Insert(L,b);Insert(L,c);Insert(L,d);Insert(L,e); //使用尾插法插入元素a,b,c,d,ePrint(L); //輸出單鏈表PrintLength(L); //輸出單鏈表長度if(SqNull(L))printf("單鏈表不為空\n");else printf("單鏈表為空\n"); //判斷單鏈表是否為空PrintData(L,3); //輸出第三個元素printf("元素a的位置：%d\n",Find(L,a)); //輸出元素a的位置ElemType f;scanf("%c",&f);Insertinto(L,4,f); //將f插入到第四個位置Print(L); //輸出單鏈表Delete(L,3); //刪除第三個元素Print(L); //輸出單鏈表free(L); //釋放內存return 0;
}
)
