存档-----------
1 #include <iostream.h>
2 typedef char ElemType;
3 #include "LinkList.h"
4 void main()
5 {
6 LinkList h;
7 ElemType e;
8 int i=0;
9 int t=0;
10 cout<<"(1)初始化单链表h\n";
11 InitList(h);
12 cout<<"(2)单链表为"<<(ListEmpty(h)?"空":"非空")<<endl;
13 cout<<"(3)依次输入字母序列,以'#'结束"<<endl;
14 cin>>e;
15 i=1;
16 while(e!='#')
17 {
18 ListInsert(h,i,e);
19 i++;
20 cin>>e;
21 }
22 cout<<"(4)输出单链表h:";
23 PrintList(h);
24 cout<<"(5)单链表h的长度="<<ListLength(h)<<endl;
25 cout<<"(5)单链表h为"<<(ListEmpty(h)?"空":"非空")<<endl;
26 cout<<"(6)测试GetElem(L,i,e)函数,请输入i的值"<<endl;
27 cin>>i;
28 t=GetElem(h,i,e);
29 if(t)
30 cout<<"(6)单链表h的第"<<i<<"个元素="<<e<<endl;
31 else
32 cout<<"(6)单链表h的第"<<i<<"个元素不存在\n";
33 cout<<"(7)测试LocateElem(L,e)函数,请输入e的值"<<endl;
34 cin>>e;
35 t=LocateElem(h,e);
36 if(t)
37 cout<<"(7)元素"<<e<<"的位置="<<t<<endl;
38 else
39 cout<<"(7)元素"<<e<<"不存在\n";
40 cout<<"(8)测试ListInsert(L,i,e)函数,请输入i的值和e的值"<<endl;
41 cout<<"请输入i的值:";
42 cin>>i;
43 cout<<"请输入e的值:";
44 cin>>e;
45 cout<<"(8)在第"<<i<<"个元素位置上插入"<<e<<"元素:";
46 t=ListInsert(h,i,e);
47 if(t)
48 cout<<"成功!\n";
49 else
50 cout<<"失败!\n";
51 cout<<"(9)输出单链表h:";
52 PrintList(h);
53 cout<<"(10)测试ListDelete(L,i,e)函数,请输入i的值"<<endl;
54 cin>>i;
55 cout<<"(10)删除h的第"<<i<<"个元素:";
56 t=ListDelete(h,i,e);
57 if(t)
58 cout<<"成功!\n";
59 else
60 cout<<"失败!\n";
61 cout<<"(11)输出单链表h:";
62 PrintList(h);
63 cout<<"(12)释放单链表h\n";
64 DestoryList(h);
65 }
1 typedef struct LNode//定义单链表结点类型
2 {
3 ElemType data;
4 struct LNode *next;
5 }LNode,*LinkList;
6 int InitList(LinkList &L)
7 {
8 //初始化只含有头结点的空的单链表
9 L=new LNode;//创建头结点
10 if(L==NULL)
11 {
12 cout<<"结点分配失败\n";
13 return 0;
14 }
15 L->next=NULL;
16 return 1;
17 }
18 void ClearList(LinkList &L)
19 {
20 //清空单链表,仅保留头结点
21 LinkList p;
22 while(L->next)
23 {
24 p=L->next;
25 L->next=p->next;
26 delete p;
27 }
28 }
29 int ListLength(LinkList L)
30 {
31 //返回单链表的长度
32 LinkList p=L;
33 int i=0;
34 while(p->next!=NULL)//数到最后一个结点为止
35 {
36 i++;
37 p=p->next;
38 }
39 return i;
40 }
41 void PrintList(LinkList L)
42 {
43 //顺序输出单链表中的各元素
44 LinkList p=L->next;
45 while(p!=NULL)
46 {
47 cout<<p->data<<" ";
48 p=p->next;
49 }
50 cout<<endl;
51 }
52 bool ListEmpty(LinkList L)
53 {
54 //判断是否为空链表
55 if(L->next==NULL)
56 return true;
57 else
58 return false;
59 }
60 int GetElem(LinkList L,int i,ElemType &e)
61 {
62 //用e返回单链表L中第i个元素的值
63 if(i<1)
64 return 0;
65 LinkList p=L->next;
66 int j=1;
67 while(j<i&&p!=NULL)
68 {
69 p=p->next;
70 j++;
71 }
72 if(p==NULL)//j<i,但p为空指针了,即i超出了[1...n]范围了
73 return 0;
74 else
75 {
76 e=p->data;
77 return 1;
78 }
79 }
80 int LocateElem(LinkList L,ElemType e)
81 {
82 //返回e元素在单链表L中的位序,若不存在,返回0
83 LinkList p=L->next;
84 int n=1;
85 while(p!=NULL&&p->data!=e)
86 {
87 p=p->next;
88 n++;
89 }
90 if(p==NULL)//直到最后也没找到等于元素e的结点
91 return 0;
92 else
93 return n;
94 }
95 int ListInsert(LinkList &L,int i,ElemType e)
96 {
97 //在单链表L的第i个数据元素之前插入数据元素e
98 if(i<1)
99 return 0;
100 int j=0;//在1号位置插入时,i-1号位置是0号位置
101 LinkList p=L,s;
102 while(j<i-1&&p!=NULL)//寻找第i-1个结点
103 {
104 p=p->next;
105 j++;
106 }
107 if(p==NULL)//未找到第i-1个结点,即i超出了[1..n+1]时
108 return 0;
109 else//找到第i-1个结点p
110 {
111 s=new LNode;//创建新结点s
112 if(s==NULL)
113 {
114 cout<<"结点分配失败\n";
115 return 0;
116 }
117 s->data=e;
118 s->next=p->next;//将s插入到p之后
119 p->next=s;
120 return 1;
121 }
122 }
123 int ListDelete(LinkList &L,int i,ElemType &e)
124 {
125 //删除单链表L中第i个结点,并用e返回其值
126 if(i<1)
127 return 0;
128 LinkList p=L,q;
129 int j=0;
130 while(j<i-1&&(p->next)!=NULL)//寻找第i-1个结点,且第i-1号元素不是最后一个元素
131 {
132 p=p->next;
133 j++;
134 }
135 if((p->next)==NULL)//未找到第i-1个结点,即i超出了[1..n]
136 return 0;
137 else//找到第i-1个结点p
138 {
139 q=p->next;//q指向要删除的结点
140 p->next=q->next;//从单链表中删除q结点
141 e=q->data;
142 delete q;//释放q结点
143 return 1;
144 }
145 }
146 void DestoryList(LinkList &L)
147 {
148 //销毁单链表
149 LinkList p;
150 while(L)
151 {
152 p=L;
153 L=L->next;
154 delete p;
155 }
156 L=NULL;
157 }
运行结果如下: