一、上机实验的问题和要求：
线性表链式存储结构下基本操作的实现（初始化、赋值、取值、插入、删除、等）。
二、基本思想，原理和算法描述：
首先基于线性表的链式存储结构建一个单链表（下面的程序实现的是通过头插法逆序建表），在此基础上实现对单链表的赋值、取值、插入、删除以及两个表的归并，需要注意的是插入（删除）过程中指针的修改。
- 源程序及注释
//线性表链式存储结构下基本操作的实现（初始化、建表、取值、插入、删除、归并等）
#include
using namespace std;
#define OK 1
#define ERROR 0
//#define ElemType int
typedef int ElemType;
typedef int Status;
typedef struct LNode{
//定义线性链表
ElemType data;
struct LNode *next;
}LNode,*linkList;
//初始化操作
Status InitList(linkList &L) {
//构造一个空的单链表L
L = new LNode;
L->next = NULL;
return OK;
}
//建表赋值
Status CreateList_H(linkList &L) {
//头插法建立单链表算法
//逆序输入n个元素的值，建立带表头结点的线性链表
int n;
cout << "请输入元素的个数：";
cin >> n;
cout << "请逆序输入元素：" << endl;
for (int i = 0; i < n; i++)
{
LNode *p = new LNode; //生成新的结点
cin >> p->data; //输入元素值
p->next = L->next;
L->next = p; //插入表头
}
return OK;
}
//遍历输出操作
Status DisplayList(linkList L) {
//遍历带头结点的单链表
LNode *p = L->next;
cout << "单链表中的元素为：" << endl;
while (p)
{
if (p->next == NULL)
{
cout << p->data;
}
else cout << p->data << " ";
p = p->next;
}
cout << endl;
return OK;
}
//取值操作
Status GetElem(linkList L, int i, ElemType &e) {
//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
LNode *p= L->next;
int j = 1; //初始化，p指向首元结点，计数器j初值赋为1
while (p && j < i) {
//顺链域向后扫描，直到p指向第i个元素或p为空
p = p->next;
++j;
}
if (!p || j > i)
{
return ERROR; //i值不合法，i>n或i<=0
}
e = p->data; //取第i个结点的数据域
return OK;
}
//插入操作
Status ListInsert(linkList &L, int i, ElemType e) {
//在带头结点的线性链表L中第i元素结点之前插入元素e
LNode *p = L;
int j = 0;
while (p&&j { p = p->next; ++j; } if (!p || j > i - 1) // i小于1或者大于n+1 { return ERROR; } LNode *s = new LNode; // 生成新结点*s s->data = e; //将新结点*s的数据域置为e s->next = p->next; p->next = s; //插入新结点 return OK; } //删除操作 Status ListDelete(linkList &L, int i, ElemType &e) { //在带头结点的单链表L中，删除第i个元素 LNode *p = L; int j = 0; while (p->next&&j { p=p->next; ++j; } if (!p->next || j > i - 1) { return ERROR; // i不合法 } LNode *q = p->next; //临时保存被删结点的地址以备释放 p->next = q->next; //删除结点 e = q->data; //保存删除结点的数据域 delete q; // 回收（释放）结点空间 return OK; } //归并操作 Status MergeList(linkList La, linkList Lb, linkList &Lc) { //按照递增顺序归并链表 LNode *p = La->next; LNode *q = Lb->next; //建立节点指针，其始终指向第三方头节点的终端节点，类似于尾插法 LNode *r = Lc; while (p != NULL && q != NULL) { //比较两指针当前指向元素的大小，小的就构成第三方链表，指针后移一位 //如果二者相等，选取任一链表的值加入第三方链表 if (p->data < q->data) { r->next = p; r = r->next; //始终指向尾节点 p = p->next; } else if (p->data == q->data) { r->next = p; r = r->next; p = p->next; q = q->next; } else { r->next = q; r = r->next; q = q->next; } if (p != NULL) { r->next = p; } if (q != NULL) { r->next = q; } } return OK; } //分隔符 Status fen_ge() { for (int f = 0; f < 3; f++) { for (int d = 0; d < 20; d++) { cout << "*"; } cout << endl; } return OK; } void main() { linkList L; //初始化操作 if (InitList(L)) { cout << "初始化成功！" << endl; } else { cout << "初始化失败！" << endl; } //建表赋值 CreateList_H(L); DisplayList(L); //取值操作 cout << "请输入想要取出第几个元素："; int i; ElemType e; cin >> i; //取出第几个元素 GetElem(L,i,e); cout << "取出的第" << i << "个元素为：" << e << endl; fen_ge(); //分割 //插入操作 int j; //第几个位置 ElemType k; //插入的元素 cout << "插入前"; DisplayList(L); cout << "请输入想要插入的位置："; cin >> j; cout << "请输入想要插入的元素："; cin >> k; ListInsert(L, j, k); fen_ge(); //分割 //删除操作 cout << "删除前"; DisplayList(L); int a; cout << "请输入想要删除元素的位置："; cin >> a; //删除元素的位置 ElemType b; ListDelete(L, a, b); cout << "删除的元素为：" << b << endl; fen_ge(); //分割 //归并操作 linkList La, Lb, Lc; //初始化操作 if (InitList(La)) { cout << "初始化La成功！" << endl; } else { cout << "初始化La失败！" << endl; } cout << "输入顺序表La的元素按值非递减排列:" << endl; CreateList_H(La); //初始化操作 if (InitList(Lb)) { cout << "初始化Lb成功！" << endl; } else { cout << "初始化Lb失败！" << endl; } cout << "输入顺序表Lb的元素按值非递减排列:" << endl; CreateList_H(Lb); //初始化操作 if (InitList(Lc)) { cout << "初始化Lc成功！" << endl; } else { cout << "初始化Lc失败！" << endl; } MergeList(La, Lb, Lc); cout << "归并后顺序表的元素按值非递减排列:" << endl; DisplayList(Lc); system("pause"); } 五、运行结果
