一、线性表例题：

例题1：求两个线性表的“并”，即LA U LB= ？

算法思路：

注意集合并的含义：

LA和LB都是无序表，则从LB种取元素逐一与LA中所有元素比较，相同则不插入LA中；

Void Union(List &LA,List LB)

{//将所有在线性表Lb中但不在La中的数据元素插入到La中

La_len=Listlength(La);

Lb_len=Listlength(Lb);

for(i=1;i<Le_len;i++)

        {

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e、

if(!LocateElem(La,e,equal))

{

ListInsert(La,++La_len,e);

                }

        }

}

算法复杂度分析：LocateElem（La,e,equal) 需La_len次比较

则整个算法需O（La_len×Lb_len）

例题2：设正整数a的前驱为PRIOR(a)，后继NEXT(a)，用递归算法计算a+b。

首先要对加法算法进行描述。不能用简单的加法语句，因为没有加法，要考虑如何用给出的两个特定函数来实现a+b？

思路: 考虑加法的定义，若用数轴来描述a+b，当a不断往"0"移动，b不断往相反方向移动的过程。当a移动到0时，b指向的位置即为a+b。

（a可视为一减计数器，前移过程中不断递减，而b的后移则是不断加1的过程）

平常我们可以用循环来实现，但根据本题题意不能用循环，而要用递归。

设计要点有二：1.递归算法的形式化描述；2.不能无限制递归，一定要有终止条件。

结果：

int add(int a,int b);

if(a==0) return(b);

else return (add(prior(a),next(b)));

若a很大，b很小怎么办？

解决方法：就从小的开始进行减计数。

二、分配动态内存：

（我的C语言专栏中介绍过基础，这里跟数据结构一起编写一些）

#define LIST_INIT_SIZE	100//存储空间的初始分配量 
#define LISTINCREMENT 	10//存储空间的分配增量
Typedef struct{
ElemType *elem;		//表基址（用指针*elem） 
int 	lenght;		//表长度（表中有多少个元素） 
int 	listsize;	//当前分配的表尺寸（字节单位） 
}SqList L;

1.动态创建一个空顺序表的算法：

Status InitList_Sq(SqList &L)

{

L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));

if(!L.elem) exit(OVERFLOW);//分配失败，结束程序

L.length=0; //暂无元素放入，空表

L.listsize = LIST_INIT_SIZE; //表尺寸=初始分配量

Return OK;

}//InitList_Sq

2.动态顺序表的插入算法：

Status ListInsert_Sq(SqList &L,int i,ElemType e)

{//在顺序线性表中第i个位置之前插入新的元素e

if(i<1||i>L.length+1) return ERROR;//检验i值得合法性

if(L.length>=L.listsize)//若表长超过表尺寸则要增加尺寸

{

newbase = (ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));//realloc（*p，newsize）函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首地址的原空间数据都拷贝进去。

if(newbase = NULL) exit(OVERFLOW); //分配失败则退出报错

L.elem = newbase; //重置新基址

L.listsize = L.listsize +LISTINCREMENT;}//增加表尺寸

q=&L.elem[i-1]; //q为插入位置。这里没有头结点的情况

for(p=L.elem[L.length-1];p>=q;--p) *(p+1)=*p;

//插入位置及之后的元素统统后移，p为元素位置

*q = e; //插入e

++L.length; //增加1个数据元素，则表长+1

return OK;

}//ListInsert_Sq

}

3.动态顺序表的删除

Status ListDelete_Sq(SqList &L,int i,ElemType &e) 
{//在顺序表L中删除第i个元素，用e返回其值 
	if(i<1||L.length) return ERROR;//i值不合法，返回 
	p=&L.elem[i-1];			//p是被删除元素的位置 
	e=*p;					//被删除元素的值赋给e 
	q=L.elem+L.length-1;	//q是表尾的位置 
	for(++p;p<=q;p++)		 
	*(p-1)=*p;				//待删除元素后面的统统前移
	--L.length;				//表长-1 
	return ok;
}//ListDelete_Sq

三、线性表的链式表示和实现

1、链表的表示

（1）链式存储结构特点：

其结点在存储器总的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。

设计效率：牺牲空间效率换取时间效率

头指针：是指向链表中第一个结点（或为头结点、或为首结点）的指针；

头结点：是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度；

首元结点：是指链表中存储线性表第一个数据元素a1的结点。

Typedef struct Lnode{
ElemType  data;		//数据域 
struct Lnode *next;	//指针域 
}Lnode,*LinkList; 	//*LinkList为Lnode类型的指针

例题1：创建链表并插入26个字母

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
	char data;
	struct node *next;
}node;

node *p,*q,*head;
int n;
int m=sizeof(node);

void build()		//字母链表的生成。要一个个慢慢链入 
{
	int i;
	head=(node*)malloc(m);// 
	p=head;
	for(i=1;i<26;i++)//因尾结点要特殊处理，故i≠26 
	{
		p->data=i+'a'-1;//第一个结点值为字符a 
		p->next=(node*)malloc(m);//为后继结点“挖坑” 
		p=p->next;	//让指针变量p指向后一个结点 
	}
	p->data=i+'a'-1;//最后一个元素要单独处理 
	p->next=NULL;	//单链表尾结点的指针域要置空 
 } 
 
void display()//字母链表的输出 
{
	p=head;
	while(p)//当指针不空时循环（仅限于无头结点的情况） 
	{
		printf("%c",p->data);
		p=p->next;
	}
 } 
 
 int main(void)
 {
 	build();
 	display();
  }

例题2：在链表中取第i个数据元素


Status GetElem_L(Linklist L,int i,ElemType &e)
{//L为带头结点的单链表的头指针
 //当第i个元素存在时，其值赋给e并返回OK，否则返回error 
	p=L->next;j=1;
//初始化，p指向第一个结点，j为计数器 
	while(p&&j<i)
	{
//顺指针向后查找，直到p指向第i个元素或p为空 
		p=p->next;++j;
	}
//第i个元素不存在 
	if(!p||j>i) return ERROR;
	e=p->data;//取第i个元素 
	return ok;
}GetElem_L

例题3：在链表中删除一个结点

Status ListDelete_L(Linklist &L,int i,ElemType e)
{//在带头结点的单链表L中，删除第i个元素，并由e返回其值 
	p=L;j=0;
	while(p->next&&j<i-1)
	{//寻找第i个结点，并令p指向其前驱 
		p=p->next;++j;
	 } 
	 if(!(p->next)p||j>i-1)	return ERROR;//删除不合理位置 
	 q=p->next;
	 p->next=q->next;//删除并释放结点 
	 e=q->data;free(q);
	 return ok;
 }