线性表的链式存储结构的实现及其应用(C/C++实现)详解编程语言

 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 }