# 线性表的链式存储结构的实现及其应用(C/C++实现)

 1 #include <iostream.h>
2 typedef char ElemType;
4 void main()
5 {
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;
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 }
19 {
20     //清空单链表，仅保留头结点
22     while(L->next)
23     {
24         p=L->next;
25         L->next=p->next;
26         delete p;
27     }
28 }
30 {
31     //返回单链表的长度
33     int i=0;
34     while(p->next!=NULL)//数到最后一个结点为止
35     {
36         i++;
37         p=p->next;
38     }
39     return i;
40 }
42 {
43     //顺序输出单链表中的各元素
45     while(p!=NULL)
46     {
47         cout<<p->data<<" ";
48         p=p->next;
49     }
50     cout<<endl;
51 }
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;
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 }
81 {
82     //返回e元素在单链表L中的位序，若不存在，返回0
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号位置
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;
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 }
147 {
148     //销毁单链表
150     while(L)
151     {
152         p=L;
153         L=L->next;
154         delete p;
155     }
156     L=NULL;
157 }

|
8天前
|

C++中的引用和指针：区别与应用

17 1
|
19天前
|
C++
C++中的封装、继承与多态：深入理解与应用
C++中的封装、继承与多态：深入理解与应用
24 1
|
2天前
|
C++
C++的引用定义语法和应用
C++的引用定义语法和应用
9 1
|
6天前
|
JSON Android开发 C++
Android c++ core guideline checker 应用
Android c++ core guideline checker 应用
9 0
|
12天前
|

C++中的结构应用：Josephus问题
C++中的结构应用：Josephus问题
10 1
|
12天前
|

C++中的结构
C++中的结构
9 2
|
18天前
|
C++ 存储 Java
C++ 引用和指针：内存地址、创建方法及应用解析
'markdown'C++ 中的引用是现有变量的别名，用 & 创建。例如：string &meal = food;。指针通过 & 获取变量内存地址，用 * 创建。指针变量存储地址，如 string *ptr = &food;。引用不可为空且不可变，指针可为空且可变，适用于动态内存和复杂数据结构。两者在函数参数传递和效率提升方面各有优势。 `
18 3
|
19天前
|

C++中的设计模式：基本概念与应用
C++中的设计模式：基本概念与应用
24 2
|
21天前
|

20 1
|
17小时前
|
C++
C++类和类模板——入门
C++类和类模板——入门
6 1