线性表的逻辑结构特征是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个开始结点，有且只能有一个终端结点，其它的结前后所相邻的也只能是一个结点(直接前趋和直接后继)。
关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。
线性表的逻辑结构和存储结构之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。
在顺序表中实现的基本运算主要讨论了插入和删除两种运算。相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。
线性表的链式存储结构。它与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。所以为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。
一个单链表由头指针的名字来命名。
对于单链表，其操作运算主要有建立单链表(头插法、尾插法和在链表开始结点前附加一个头结点的算法)、查找(按序号和按值)、插入运算、删除运算等。以上各运算的平均时间复杂度均为O(n).其主要时间是耗费在查找操作上。
循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点)，形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表了。
判别链表终止的条件也不同于单链表，它是以指针是否等于某一指定指针如头指针或尾指针来确定。
双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,这样形成的链表就有两条不同方向的链。使得从已知结点查找其直接前趋结点可以和查找其直接后继结点的时间一样缩短为O(1)。
双链表一般也由头指针head惟一确定。双链表也可以头尾相链接构成双(向)循环链表。
关于顺序表和链表的比较，请看下表：
|
具体要求 |
顺序表 |
链表 |
| 基于空间 |
适于线性表长度变化不大，易于事先确定其大小时采用。 |
适于当线性表长度变化大，难以估计其存储规模时采用。 |
| 基于时间 |
由于顺序表是一种随机存储结构，当线性表的操作主要是查找时，宜采用。 |
链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。 |
试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
答：
开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。
在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?
我们分别讨论三种链表的情况。
1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。
3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。
算法如下:
LinkList Link( LinkList L1 , LinkList L2 )
{
//将两个单链表连接在一起
ListNode *p , *q ;
p=L1;
q=L2;
while ( p->next ) p=p->next; //查找终端结点
p->next = q->next ; //将L2的开始结点链接在L1之后
return L1 ;
}
本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：
m+1=O(m)
设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。
根据已知条件，A和B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。
算法如下：
LinkList MergeSort ( LinkList A , LinkList B )
{
// 归并两个递增有序表为一个递减有序表
ListNode *pa , *pb , *qa , *qb ;
pa=A;
pb=B ;
qa=A->next;
qb=B->next;
while ( qa && qb)
{
if ( qb->data < qa->data )
{
// 当B中的元素小于A中当前元素时，插入到它的前面
pb=qb;
qb=qb->next ;// 指向B中下一元素
pa->next=pb;
pb->next=qa;
pa=pb;
}
else if ( qb->data >= pa->data && qb->data <= qa->data)
{
// 当B中元素大于等于A中当前元素
// 且小于等于A中后一元素时，
// 将此元素插入到A的当前元素之后
pa=qa;
qa=qa->next; // 保存A的后一元素位置
pb=qb;
qb=qb->next; // 保存B的后一元素位置
pa->next=pb; //插入元素
pb->next=qa;
}
else
{
// 如果B中元素总是更大,指针移向下一个A元素
pa=qa;
qa=qa->next;
}
}
if ( qb ) // 如果A表已到终端而B表还有结点未插入
{
// 将B表接到A表后面
pa->next=qb;
}
LinkList C=ReverseList ( A );// 调用前面2.8题所设计的逆置函数
return C; //返回新的单链表C, 已是递减排列
}
该算法的时间复杂度分析如下：
算法中只有一个while 循环，在这个循环中，按照最坏的情况是B元素既有插到A的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时的所费时间就是m+n. 而新链表的长度也是m+n+1 (有头结点)，这样逆置函数的执行所费时间为m+n+1.所以可得整个算法的时间复杂度为：
m+n+m+n+1=2(m+n)+1= O(m+n)
---------------------------------------------------------------------------------------------------------
//ListStruct.h 将链表结构存为头文件
typedef char DataType; //假设结点的数据类型是字符型
typedef struct node { //结点类型定义
DataType data;
struct node *next;//结点的指针域
}ListNode;
typedef ListNode * LinkList;
// 以下是源文件 // 在VC++中运行通过。
#include <iostream.h>
#include <stdio.h>
#include "ListStruct.h"
#include <malloc.h>
LinkList CreatList (void)
{ //用尾插法建立带头结点的单链表
char ch;
LinkList head = (LinkList)malloc(sizeof( ListNode)); //生成头结点
ListNode *s , *r;
r=head;//尾指针亦指向头结点
while ((ch=getchar())!='\n')
{
s=(ListNode *) malloc (sizeof(ListNode));
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
return head;
}
void OutList( LinkList L)
{
ListNode *p;
p=L;
while (p->next)
{
cout << p->next->data << " " ;
p=p->next;
}
cout << endl;
}
LinkList ReverseList( LinkList head )
{
// 将head 所指的单链表逆置
ListNode *p ,*q ;//设置两个临时指针变量
if( head->next && head->next->next) //当链表不是空表或单结点时
{
p=head->next;
q=p->next;
p -> next=NULL; //将开始结点变成终端结点
while (q)
{ //每次循环将后一个结点变成开始结点
p=q;
q=q->next ;
p->next = head-> next ;
head->next = p;
}
return head;
}
return head; //直接返回head
}
LinkList MergeSort ( LinkList A , LinkList B )
{
// 归并两个递增有序表为一个递减有序表
ListNode *pa , *pb , *qa , *qb ;
pa=A;
pb=B ;
qa=A->next;
qb=B->next;
while ( qa && qb)
{
if ( qb->data < qa->data )
{
// 当B中的元素小于A中当前元素时，插入到它的前面
pb=qb;
qb=qb->next ;// 指向B中下一元素
pa->next=pb;
pb->next=qa;
pa=pb;
}
else if ( qb->data >= pa->data && qb->data <= qa->data)
{
// 当B中元素大于等于A中当前元素
// 且小于等于A中后一元素时，
// 将此元素插入到A的当前元素之后
pa=qa;
qa=qa->next; // 保存A的后一元素位置
pb=qb;
qb=qb->next; // 保存B的后一元素位置
pa->next=pb; //插入元素
pb->next=qa;
}
else
{
// 如果B中元素总是更大,指针移向下一个A元素
pa=qa;
qa=qa->next;
}
}
if ( qb ) // 如果A表已到终端而B表还有结点未插入
{
// 将B表接到A表后面
pa->next=qb;
}
LinkList C=ReverseList ( A );// 调用前面2.8题所设计的逆置函数
return C; //返回新的单链表C, 已是递减排列
}
void main()
{
LinkList A, B, C;
A=CreatList();
OutList (A);
B=CreatList();
OutList (B);
C=MergeSort (A ,B);
OutList (C);
}
---------------------------------------------------
我的算法思路为：当A、B都不空时，各取A、B表中的第一个结点比较，哪个值小，就把它用头插法插入C表。（利用原来的头结点，始终是取第一个结点比较）继续取值比较。当A表为空，或B表为空，则把剩余结点用头插法插入C表。
void LinkList(Nodetype *A,Nodetype *B, Nodetype **C)
{//假设A和B已建立，C表的头结点已初始化
Nodetype *p, *q;
p=A->Next;
q=B->Next;
while(p&&q)//两表中都有数
{
if(p->Data<q->Data)//如A中的结点值大于B中结点值
{
A->Next=p->Next;//A指向A表的下一个结点
p->Next=C->Next;//把P的结点用头插法，插入C表。
C->Next=p;
p=A->Next;//P指向A表的第一个结点，继续比较
}
else
{
B->Next=q->Next;//算理同上面
q->Next=C->Next;
C->Next=q;
q=B->Next;
}
}
if(p)//如A表还有结点，则把剩余结点，用头插法插入C表
{
while(p)
{
A->Next=p->Next;
p->Next=C->Next;
C->Next=p;
p=A->Next;
}
}
else
if(q)//如B表还有结点，则把剩余结点，用头插法插入B表
{
while(q)
{
B->Next=q->Next;
q->Next=C->Next;
C->Next=q;
q=B->Next;
}
}
free(A);//释放原头结点空间
free(B);
}
你的算法要排表两次，第一次为插入，第二次为逆序。