单链表

一世轻尘

1. #include<iostream>
   
2. #include<cstdlib>
   
3. #define LEN sizeof(struct linklist)
   
4. 
   
5. using namespace std;
   
6. 
   
7. typedef int ElemType;
   
8. typedef struct linklist{
   
9.         ElemType data;
   
10.         struct linklist *next;
    
11. }Node,*LinkList;
    
12. 
    
13. int length,num,i;
    
14. void InitList(LinkList *L);//初始化链表
    
15. void DestroyList(LinkList *L);//销毁链表
    
16. void ClearList(LinkList *L);//清空链表
    
17. void GetElem(LinkList L,int i,ElemType *e);//获取元素
    
18. void ListInsert(LinkList *L,int i,ElemType e);//插入元素结点
    
19. void ListDelete(LinkList *L,int i,ElemType *e);//删除元素结点
    
20. void ShowList(LinkList L);//输出链表
    
21. int ListLength(LinkList L);//求表长
    
22. void Error(char *s);//报错信息
    
23. Node *LocateElem(LinkList L,ElemType e);//定位元素位置
    
24. 
    
25. 
    
26. int main()
    
27. {
    
28. 
    
29. }
    
30. 
    
31. //初始化链表
    
32. void InitList(LinkList *L)
    
33. {
    
34.         *L=(Node*)malloc(LEN);
    
35.         (*L)->next=NULL;
    
36. }
    
37. 
    
38. //销毁链表
    
39. void DestroyList(LinkList *L)
    
40. {
    
41.         Node *p;//定义一个结点指针，指向待销毁的结点
    
42.         while(*L)
    
43.         {
    
44.                 p=*L;
    
45.                 *L=(*L)->next;
    
46.                 free(p);
    
47.         }
    
48. }
    
49. 
    
50. //清空链表
    
51. void ClearList(LinkList *L)
    
52. {
    
53.         Node *p=(*L)->next,*q;//从第一个结点开始释放，保留头结点
    
54.         while(p)
    
55.         {
    
56.                 q=p;
    
57.                 p=p->next;
    
58.                 free(q);
    
59.         }
    
60.         (*L)->next=NULL;
    
61. }
    
62. 
    
63. //求表长
    
64. int ListLength(LinkList L)
    
65. {
    
66.         int length=0;//计数器
    
67.         Node *p = L;
    
68.         while(p->next)
    
69.         {
    
70.                 length++;
    
71.                 p=p->next;
    
72.         }
    
73.         return length;
    
74. }
    
75. 
    
76. //获取元素
    
77. void GetElem(LinkList L,int i,ElemType *e)
    
78. {
    
79.         Node *p=L->next;
    
80.         int j=1;
    
81.         while(p&&(j<i))
    
82.         {
    
83.                 p=p->next;
    
84.                 j++;
    
85.         }
    
86.         if(!p||(j>i))
    
87.                 Error("Position Error!");
    
88.         else
    
89.                 *e = p->data;
    
90. }
    
91. 
    
92. //定位元素位置
    
93. Node *LocateElem(LinkList L,ElemType e)
    
94. {
    
95.         Node *p=L->next;//设置指针，初始时指向链表第一个结点
    
96.         while(p&&(p->data!=e))//顺链向后扫描
    
97.                 p=p->next;
    
98.         return p;//返回要查找的元素指针
    
99. }
    
100. 
     
101. //插入元素
     
102. void ListInsert(LinkList *L,int i,ElemType e)
     
103. {
     
104.         Node *p = *L;
     
105.         int j = 0;
     
106.         while(p && (j < i-1) )
     
107.         {
     
108.                 p = p->next;
     
109.                 j++;
     
110.         }//运行完后p指向第i-1个结点
     
111.         if(!p||(j>i-1))
     
112.                 Error("Position Error!");
     
113.         else//插入第i个结点
     
114.         {
     
115.                 Node *s=(Node*)malloc(LEN);
     
116.                 s->data=e;//赋值
     
117.                 s->next=p->next;
     
118.                 p->next=s;
     
119.         }
     
120. }
     
121. 
     
122. //删除元素并返回其数据域的值
     
123. void ListDelete(LinkList *L,int i,ElemType *e)
     
124. {
     
125.         Node *p = *L,*q;
     
126.         int j=0;
     
127.         while((p->next)&&(j<i-1))
     
128.         {
     
129.                 p=p->next;
     
130.                 j++;
     
131.         }//运行完后指向第i-1个结点
     
132.         if(!(p->next)||(j>i-1))
     
133.                 Error("Position Error!");
     
134.         q=p->next;
     
135.         *e=q->data;
     
136.         p->next=q->next;
     
137.         free(q);
     
138. }
     
139. 
     
140. //输出链表
     
141. void ShowList(LinkList L)
     
142. {
     
143.         Node *p=L->next;
     
144.         while(p)
     
145.         {
     
146.                 cout << p->data;
     
147.                 p = p->next;
     
148.         }
     
149. }
     
150. 
     
151. //报错信息
     
152. void Error(char *s)
     
153. {
     
154.     cout << s << endl;//输出错误信息提示
     
155.     exit(1);//退出程序
     
156. }

复制代码