数据结构——实验01-线性表的链式存储和操作

一、实验内容

二、算法思想与算法实现

1、解题思想

（1）逆序创建链表La就是使用头插法创建一个链表，所谓头插法就是在创建链表时始终将新元素插入到头结点之后，而正序创建链表Lb就是使用尾插法创建一个链表，所谓尾插法创建一个链表就是在创建链表时始终将新元素插入到表尾

（2）合并两个升序序列，这个算法很基础，这里不做叙述，需要注意的是由于在创建La时我们是逆序创建的，也就是说此时La是降序排列，所以在做两个链表的合并操作之前我们需要先将链表La逆置

（3）删除Lc中的多余元素：这里我们可以用一个指针p表示当前链表的结点，然后用一个指针t指向第一个结点元素值不等于当前结点元素值的结点，然后让结点p的next指针域指向t即可，如下图所示

（4）逆置一个链表，可以借助头插法创建链表的思想，即扫描当前需要逆置的链表不断将当前结点插入到表头

2、算法实现

（1）定义链表结点

//定义链表节点
typedef struct LNode {int data;                          //数据域struct LNode* next;                //指针域
}LNode,*LinkList;

（2）头插法创建链表

//使用头插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_HeadInsert(LinkList& L) {//对链表进行初始化操作L = (LNode*)malloc(sizeof(LNode) * 1);if (L == NULL){return false;}L->next = NULL;LNode* p = NULL;int inputs = 0;printf("请输入链表元素:\n");while (1){scanf("%d", &inputs);if (inputs == 666)break;p = (LNode*)malloc(sizeof(LNode) * 1);if (p == NULL){return false;}p->data = inputs;p->next = L->next;L->next = p;}return true;
}

 （3）尾插法创建链表

//使用尾插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_TailInsert(LinkList& L)
{//对链表进行初始化操作L = (LNode*)malloc(sizeof(LNode) * 1);if (L == NULL)return false;L->next = NULL;LNode* p, * t;   //p指针用于建立新结点，t用于指向当前链表的尾结点int inputs;t = L;printf("请输入链表元素:\n");while (1){scanf("%d", &inputs);if (inputs == 666)break;p = (LNode*)malloc(sizeof(LNode) * 1);if (p == NULL)return false;p->data = inputs;p->next = NULL;t->next = p;t = p;}return true;
}

（4）合并两个升序链表

//合并两个有序链表
bool Merge_SortedLinkList(LinkList La, LinkList Lb, LinkList& Lc)
{LNode* a, * b, * c, * t;a = La->next;b = Lb->next;//初始化链表Lc；Lc = (LNode*)malloc(sizeof(LNode) * 1);if (Lc == NULL)return false;Lc->next = NULL;t = Lc;          //t指针指向Lc的尾部结点while (a != NULL && b != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);if (c == NULL)return false;if (a->data <= b->data){c->data = a->data;c->next = NULL;t->next = c;t = c;a = a->next;}else{c->data = b->data;c->next = NULL;t->next = c;t = c;b = b->next;}}while (a == NULL && b != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);c->data = b->data;c->next = NULL;t->next = c;t = c;b = b->next;}while (b == NULL && a != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);c->data = a->data;c->next = NULL;t->next = c;t = c;a = a->next;}return true;
}

（5）删除链表中的重复元素

//删除有序链表中的重复元素
bool DeleteRpeatElem(LinkList& L)
{//判断是否是空表if (L->next == NULL)return false;LNode* p, * e = NULL;   //p指针用于记录当前结点，e指针用于表示值等于当前结点的最后一个结点p = L->next;while (p != NULL){e = p->next;if (e == NULL)break;while (p->data == e->data){LNode* temp = e;e = e->next;free(temp);}p->next = e;p = p->next;	}return true;
}

（6）逆置一个链表

//逆置一个链表，从头开始扫描一个链表，不断将当前结点插入到链表的开始位置
bool ReverseLinkList(LinkList& L)
{if (L->next == NULL)return false;LNode* end = L->next;  //指向逆置以后的表尾元素LNode* p = end->next;  //指向当前元素while (p != NULL){LNode* temp = p->next;p->next = L->next;L->next = p;p = temp;}end->next = NULL;return true;
}

三、代码测试

完整测试代码：

//用C语言编写程序，其中Lb={2,4,6,8,10} La={1,2,3,4,5,6,8},
//(1)逆序创建链表La, 正序创建链表Lb; .
//(2)将La与Lb有序合并，得到有序链表Lc：Lc = { 1,2,2,3,4,4,5,6,6,8,8,10 }
//(3)删除Lc中多余的重复元素，使得所有元素只保留一个;
//(4)将链表Lc倒置，并输出其内容。#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
using namespace std;//定义链表节点
typedef struct LNode {int data;                          //数据域struct LNode* next;                //指针域
}LNode,*LinkList;//使用头插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_HeadInsert(LinkList& L) {//对链表进行初始化操作L = (LNode*)malloc(sizeof(LNode) * 1);if (L == NULL){return false;}L->next = NULL;LNode* p = NULL;int inputs = 0;printf("请输入链表元素:\n");while (1){scanf("%d", &inputs);if (inputs == 666)break;p = (LNode*)malloc(sizeof(LNode) * 1);if (p == NULL){return false;}p->data = inputs;p->next = L->next;L->next = p;}return true;
}//使用尾插法创建一个带头结点的链表，当用户输入666时表示链表创建结束
bool List_TailInsert(LinkList& L)
{//对链表进行初始化操作L = (LNode*)malloc(sizeof(LNode) * 1);if (L == NULL)return false;L->next = NULL;LNode* p, * t;   //p指针用于建立新结点，t用于指向当前链表的尾结点int inputs;t = L;printf("请输入链表元素:\n");while (1){scanf("%d", &inputs);if (inputs == 666)break;p = (LNode*)malloc(sizeof(LNode) * 1);if (p == NULL)return false;p->data = inputs;p->next = NULL;t->next = p;t = p;}return true;
}//合并两个有序链表
bool Merge_SortedLinkList(LinkList La, LinkList Lb, LinkList& Lc)
{LNode* a, * b, * c, * t;a = La->next;b = Lb->next;//初始化链表Lc；Lc = (LNode*)malloc(sizeof(LNode) * 1);if (Lc == NULL)return false;Lc->next = NULL;t = Lc;          //t指针指向Lc的尾部结点while (a != NULL && b != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);if (c == NULL)return false;if (a->data <= b->data){c->data = a->data;c->next = NULL;t->next = c;t = c;a = a->next;}else{c->data = b->data;c->next = NULL;t->next = c;t = c;b = b->next;}}while (a == NULL && b != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);c->data = b->data;c->next = NULL;t->next = c;t = c;b = b->next;}while (b == NULL && a != NULL){c = (LNode*)malloc(sizeof(LNode) * 1);c->data = a->data;c->next = NULL;t->next = c;t = c;a = a->next;}return true;
}//删除有序链表中的重复元素
bool DeleteRpeatElem(LinkList& L)
{//判断是否是空表if (L->next == NULL)return false;LNode* p, * e = NULL;   //p指针用于记录当前结点，e指针用于表示值等于当前结点的最后一个结点p = L->next;while (p != NULL){e = p->next;if (e == NULL)break;while (p->data == e->data){LNode* temp = e;e = e->next;free(temp);}p->next = e;p = p->next;	}return true;
}//逆置一个链表，从头开始扫描一个链表，不断将当前结点插入到链表的开始位置
bool ReverseLinkList(LinkList& L)
{if (L->next == NULL)return false;LNode* end = L->next;  //指向逆置以后的表尾元素LNode* p = end->next;  //指向当前元素while (p != NULL){LNode* temp = p->next;p->next = L->next;L->next = p;p = temp;}end->next = NULL;return true;
}//顺序打印一个链表中的所有元素
bool PrintLinkList(LinkList L)
{if (L->next == NULL)return false;LNode* p = L->next;while (p != NULL){printf("%d\t", p->data);p = p->next;}printf("\n");return true;
}//测试程序
int main()
{LinkList La, Lb, Lc;//逆序创建链表La,即使用头插法创建链表LaList_HeadInsert(La);printf("链表La：\n");PrintLinkList(La);//正序创建链表Lb，即使用尾插法创建链表LbList_TailInsert(Lb);printf("链表Lb：\n");PrintLinkList(Lb);//合并La和Lb//先逆序LaReverseLinkList(La);printf("逆序后的链表La：\n");PrintLinkList(La);//调用函数合并La和LbMerge_SortedLinkList(La, Lb, Lc);printf("合并链表La和链表Lb得到的链表Lc：\n");PrintLinkList(Lc);//删除Lc中的重复元素DeleteRpeatElem(Lc);printf("删除链表Lc中的重复元素的结果：\n");PrintLinkList(Lc);//将Lc逆序ReverseLinkList(Lc);printf("将链表Lc逆序之后的结果：\n");PrintLinkList(Lc);return 0;}

测试结果截图：