/* LinkList.c * 线性表的链式实现,并有相应的创建、插入、删除、定位、求长、获取元素操作 * Author: Jeff Chen * Date:2012-4-13 */ #include<stdio.h> #include<stdlib.h> #define ElemType int typedef struct Lnode { ElemType data; struct Lnode *next; }Lnode,*LinkList; ElemType GetElem_L(LinkList L,int i) {//获取第i个元素的值 LinkList p; p=L->next; int j=1; while(p&&j<i) { p=p->next; j++; } if(!p||j<i) return -1; return p->data; } void InsertElem_L(LinkList p,int i,ElemType e) {//在表的第i个元素前插入e int j=0; while(p&&j<i-1) { p=p->next; j++; } if(!p||j>i-1) exit(0); LinkList newNode=(LinkList)malloc(sizeof(Lnode)); newNode->next=p->next; newNode->data=e; p->next=newNode; } void ListDel_L(LinkList p,int i) {//删除表中第i个元素 int j=0; while(p->next&&j<i-1) { p=p->next; j++; } if(!(p->next)||j>i-1) exit(0); LinkList q=p->next; p->next=q->next; free(q); } int ListLen_L(LinkList L) {//求表的长度 LinkList p; int i=0; p=L->next; while(p){ i++; p=p->next; } return i; } int Locate_L(LinkList L,ElemType e) {//定位元素e在表中的位置 LinkList p; int i=1; p=L->next; while(p&&p->data!=e){ p=p->next; i++; } if(!p) return -1; return i; } LinkList CreatList_L(LinkList L,int n) {//逆序输入n个元素的值,建立一个带头结点的单链表L LinkList p; L=(LinkList)malloc(sizeof(Lnode)); L->next=NULL; int i; for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(Lnode)); scanf("%d",&(p->data)); p->next=L->next; L->next=p; } return L; } void display(LinkList L) { LinkList p; p=L->next; printf("\n-----------data--------------\n"); if(!(p->next)) printf("null!\n"); while(p) { printf("%d ",p->data); p=p->next; } } int main() { LinkList L; ElemType num; int l; printf("How long is the LinkList?\n"); scanf("%d",&l); int i; printf("Enter the data:\n"); L=CreatList_L(L,l); display(L); //显示新创建的链表 printf("\nThe 1st is %d\n",GetElem_L(L,1)); //获取第一个元素 InsertElem_L(L,1,3); printf("\n-------After Insert--------\n"); display(L); //显示插入后的链表 ListDel_L(L,1); printf("\n-------After Delete--------\n"); display(L); printf("\nlength=%d\n",ListLen_L(L));//显示长度 printf("The 3th is %d\n",Locate_L(L,3));//定位 return 0; }
运行与测试:
How long is theLinkList?
10
Enter the data:
10 9 8 7 6 5 43 2 1
-----------data--------------
1 2 3 4 5 6 7 8 9 10
The 1st is 1
-------AfterInsert--------
-----------data--------------
3 1 2 3 4 5 6 7 8 9 10
-------AfterDelete--------
-----------data--------------
1 2 3 4 5 6 7 8 9 10
length=10
The 3th is 3