1：线性表及其应用 （1）： 顺序表操作验证（包括建立、查找、插入、删除、销毁等操作） （2）：单链表操

Question

1：线性表及其应用
（1）： 顺序表操作验证（包括建立、查找、插入、删除、销毁等操作）
（2）：单链表操作验证（包括建立、查找、插入、删除、销毁等操作）
（3）：单链表的归并合并算法和双链表的插入删除操作。
（4）：链表应用：已知非空线性链表第一个链结点的指针为list，写出下列各项操作的算法程序。（1）逆转该线性链表；（2）删除线性链表中从左往右第一个数据为data的链结点；（3）删除从第i个链结点开始的连续k个结点。
要求：
（1）设计一组输入数据并编写完整的程序。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。程序具有可扩展性。
（2）要求设计的界面美观、合理、便于操作等，功能与实际应用系统紧密联系，系统结构合理构思巧妙、模块化程度高等。

Answer 1

随便找本算法书都有啊

Answer 2

我没有逆转链表的程序，但是严蔚敏习题集有道题好像可以解决这个问题，提供我自己写的c++代码，希望可以帮助你！
（1）顺序表
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

typedef int ElemType;

#define LIST_INIT_SIZE 10
#define LISTINCREMENT 2
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;

Status InitList_Sq(SqList &L)
{
// 构造一个空的线性表L。
L.elem = new ElemType[LIST_INIT_SIZE];
if (!L.elem) return OVERFLOW; // 存储分配失败
L.length = 0; // 长度为0
L.listsize = LIST_INIT_SIZE; // 初始存储容量
return OK;
} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
ElemType *p,*q;
if (i < 1 || i > L.length+1) return ERROR;
q = &(L.elem[i-1]); // q指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p;
// 插入位置及之后的元素右移
*q = e; // 插入e
++L.length; // 表长增1
return OK;
} // ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
ElemType *p,*q;
if ((i < 1) || (i > L.length)) return ERROR;
p = &(L.elem[i-1]); // p为被删除元素的位置
e = *p; // 被删除元素的值赋给e
q = L.elem+L.length-1; // 表尾元素的位置
for (++p; p <= q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移
--L.length; // 表长减1
return OK;
} // ListDelete_Sq

void Create_Sq(SqList &L)
{
cout<<"请输入元素个数:";
cin>>L.length;
cout<<"创建顺序表"<<endl;
for(int i=0;i<L.length;i++)
{
cout<<"请输入第"<<i+1<<"个数：";
cin>>L.elem[i];
}
}

void Print_Sq(SqList &L)
{
cout<<"输出顺序表:"<<endl;
for(int i=0;i<L.length;i++) cout<<L.elem[i]<<" ";
}

（2）链表
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

#include <iostream>
#include <stdlib.h>
#include <iomanip>
using namespace std;

typedef int Status;
typedef int ElemType;

typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;

void InitList_L(LinkList &L)
{
L = new LNode;
if (!L)
cout<<"内存分配失败";
else
L->next = NULL;
}

void CreatList_L(LinkList &L)
{
LNode *p,*q;
int n;
//cout<<"请输入元素的个数：";
cin>>n;
L=new LNode;
L->next=NULL; p=L;
for(int i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"个数：";
q=new LNode;
cin>>q->data;
q->next=p->next; p->next=q; p=q;
}
}

void DestroyList_L(LinkList &L)
{
LNode *p;
while (L)
{
p=L; L=L->next; delete p;
}
}

Status GetElem_L(LinkList L, int i, ElemType &e)
{
LNode *p; int j;
p = L->next; j = 1;
while (p && j<i)
{
p = p->next; ++j;
}
if ( !p || j>i ) return ERROR;
e = p->data;
return OK;
}

void ListPrint_L(LinkList L)
{
LNode *p;
p=L->next;
//cout<<"链表的内容为:";
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}

Status ListInsert_L(LinkList &L, int i, ElemType e)
{
LNode *p,*s; int j;
p = L; j = 0;
while (p && j <i-1)
{
p = p->next; ++j;
}
if (!p || j > i-1) return ERROR;
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}

Status ListDelete_L(LinkList L, int i, ElemType &e)
{
LNode *p,*q; int j;
p = L; j = 0;
while (p->next && j < i-1)
{
p = p->next; ++j;
}
if (!(p->next) || j > i-1)
return ERROR; // 删除位置不合理
q = p->next; p->next = q->next; // 删除并释放结点
e = q->data; delete(q);
return OK;
}
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) {
LNode *pa,*pb,*pc;
pa=La->next; pb=Lb->next;
Lc=pc=La;//用La的头结点作为Lc的头结点
while(pa&&pb){
if(pa->data<=pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}
else{
pc->next=pb;pc=pb;pb=pb->next;
}
}
pc->next=pa?pa:pb;//插入剩余段
delete(Lb); //释放Lb的头结点
}
以下是它的主函数
#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include"LinkList.h"
using namespace std;
int main(){
LinkList La,Lb,Lc;
LNode *pa,*pb,*pc;
cout<<"请输入链表La元素个数："<<endl;
CreatList_L(La);
cout<<"请输入链表Lb元素个数："<<endl;
CreatList_L(Lb);
InitList_L(Lc);
MergeList_L(La,Lb,Lc);
cout<<"链表Lc内容为："<<endl;
ListPrint_L(Lc);
system("PAUSE");
return 0;
}
经过DEV-c编译通过，在VC可能会有点小错误，改改就好。