第2章 线性表的链式表示
综合应用题 第2题
#include <stdio.h>
#include <stdlib.h> //malloc所在头文件
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct node {
ElemType data; //单链表中的数据域
struct node *next; //单链表的指针域
}LNode, *LinkList;
//带头结点单链表的初始化
LinkList LinkListInit() {
LNode *L;
L = (LNode *)malloc(sizeof(LNode)); //申请结点空间
if (L == NULL) { //判断是否有足够的内存空间
cout<<"申请内存空间失败\n";
exit(0);
}
L->next = NULL; //将next设置为NULL,初始长度为0的单链表
return L;
}
//单链表的建立1,头插法建立带头结点的单链表
/*思路:1.单链表的初始化
2.分别分配n个结点
3.对每个结点:数据域赋值;指针域指向头结点L指向的下一个结点,并使头结点指向该结点
*/
LinkList LinkListCreatH(ElemType *a,int n) {
LNode *L;
L = LinkListInit(); //初始化一个空链表
LNode *p;
for (int i = 0; i < n; i++){
p = (LNode *)malloc(sizeof(LNode)); //申请新的结点
if (p == NULL) { //判断是否有足够的内存空间
printf("申请内存空间失败\n");
exit(0);
}
//核心
p->data = a[i]; //结点数据域赋值
p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL
L->next = p;
}
return L;
}
//单链表的建立2,尾插法建立带头结点的单链表
/*思路:1.单链表的初始化
2.定义一个始终指向终端节点的结点r,开始时赋值为头结点
3.对每个结点:数据域赋值;指针域指向r指向的下一个结点,并使r指向该结点,r等于该结点
*/
LinkList LinkListCreatT(ElemType *a, int n) {
LNode *L;
L = LinkListInit(); //初始化一个空链表
LNode *r;
r = L; //r始终指向终端结点,开始时指向头结点
LNode *p;
for (int i = 0; i < n; i++){
p = (LNode *)malloc(sizeof(LNode)); //申请新的结点
if (p == NULL) { //判断是否有足够的内存空间
cout<<"申请内存空间失败\n";
exit(0);
}
p->data = a[i]; //结点数据域赋值
p->next = r->next;
r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL
r = p;
}
return L;
}
bool del_x(LinkList &L,ElemType x){
LNode *pre=NULL,*cur=L->next;
while(cur!=NULL)
{
if(cur->data==x)
{
pre->next=cur->next;
delete cur;
cur=pre->next;
}
else{
pre=cur;
cur=cur->next;
}
}
}
int main() {
LinkList list, start;//, listverse;
int array[8] = { 1, 2, 5, 4, 5, 6, 7, 8 };
cout<<"输出单链表的数据:";
list=LinkListCreatT(array,8);
for (start = list->next; start != NULL; start = start->next) {
cout<<start->data<<" ";
}
cout<<endl;
ElemType x;
cout<<"请输入要删除的元素的值:";
cin>>x;
del_x(list,x);
for (start = list->next; start != NULL; start = start->next) {
cout<<start->data<<" ";
}
cout<<endl;
return 0;
}