线性表代码总结

1. 线性表的结构体定义

1.1 顺序表的结构体定义

#define maxSize 100 //整型常量

typedef struct{
	int data[maxSize];   //存放顺序表元素的数组
	int length;          //存放顺序表的长度
}SqList;                 //顺序表类型定义

但考试使用最多的顺序表的定义如下：

int A[maxSize];
int n;

如上两行定义了一个长度为n，表内元素为整数的顺序表。

1.2 单链表结点定义

typedef struct LNode{
	int data;              //data中存放结点数据域
	struct LNode *next;    //指向后继结点的指针
}LNode；                   //定义单链表结点类型

1.3 双链表结点定义

typedef struct DLNode{
	int data;
	struct DLNode *prior;  //指向前驱结点的指针
	struct DLNode *next;   //指向后继结点的指针
}DLNode;

什么是结点？
结点即内存中由用户分配的一块空间，只有一个地址来表示结点的存在与否，所以在为链表分配空间的时候，会同时定义一个指针，存储这片空间的地址（即指针指向结点），并将此指针名称作为结点的名称。

LNode *addr=(LNode*）malloc(sizeof(LNode));

即分配了一片LNode型空间，也就是一个LNode型结点。并定义一个名为addr的指针指向这个结点。同时，addr也作为该结点的名字。addr命名包含两个东西：第一，结点；第二，是指向这个结点的指针。

2. 顺序表的操作

2.1 按元素值的查找算法

/**
查找第一个值等于e的元素，并返回其下标
*/
int findElem(SqList L,int e){
	for(int i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i;   //找到，返回下标
	return -1;          //未找到，返回-1,作为失败标志
}

2.2 插入数据元素

/**
顺序表的第p个位置插入新的元素e
*/
int insertElem(SqList &L,int p,int e){  //L本身要改变，采用引用
	if(p<0||p>L.length||L.length==maxSize)  //插入位置不合法
		return 0;
	for(int i=L.length-1;i>=p;i--)
		L.data[i+1]=L.data[i];     //从p开始元素后移
	L.data[p]=e;            //将元素e插入到位置p上
	++(L.length);
	return 1;               //插入成功，返回1
}

2.3 删除数据元素

/**
删除表中下标为p的元素，成功返回1，否则返回0，并将删除的元素赋值给e
*/
int deleteElem(SqList &L,int p,int &e){
	if(p<0||p>L.length)
		return 0;
	e=L.data[p];          //将被删除的元素赋值给e
	for(int i=p;i<L.length-1;i++)   //从p位置开始，将后边元素前移
		L.data[i]=L.data[i+1];
		--(L.length);     //表长减1
		return 1;
}

3. 单链表的操作

3.1 尾插法建立单链表

/**
n个元素存储在数组a中，尾插法建立链表C
*/
void createListT(LNode *&C,int a[],int n){
	LNode *s,*r;     //s指向新申请的结点，r始终指向C的终端结点
	C=(LNode*)malloc(sizeof(LNode));      //申请头结点空间
	C->next=NULL;
	r=C;             //r指向头结点,此时头结点即是终端结点
	for(int i=0;i<n;i++){
		s=(LNode*)malloc(sizeof(LNode));   //s指向新申请的结点
		s->data=a[i];   
		r->next=s;     //用r来接纳新结点
		r=r->next;     //r指向终端结点,以便接受新的结点
	}
	r->next=NULL;     //终端结点指针域置空，链表建立完成
}

3.2 头插法建立单链表

void createListH(LNode *&C,int a[],int n){
	LNode *s;
	C=(LNode*)malloc(sizeof(LNode));      //申请头结点空间
	C->next=NULL;
	for(int i=0;i<n;i++){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=a[i];
   		s->next=C->next;  //s所指新结点指针域next指向C中的开始结点
		C->next=s;        //头结点的指针域next指向s结点，使得s称为新的开始结点   
	}
}

该算法不断将新结点插入到链表前端，因此新建立的链表中元素的次序和数组a中元素的次序是相反的。

3.3 合并两个单链表

/**
A,B两个递增单链表（带头结点），将其归并成一个按元素值非递减
有序的链表C。
*/
void merge(LNode *A,LNode *B,LNode *&C){
	LNode *p=A->next;     //
	LNode *q=B->next;     //
	LNode *r;             //r始终指向C的终端结点
	C=A;                  //用A的头结点作为C的头结点
	C->next=NULL;         //从A链表取下头结点作为新链表的头
	free(B);              //B的头结点已无用，释放
	r=C;                  //r指向C，此时头结点也是终端节点
	while(p!=NULL&&q!=NULL){
		if(p->data<=q->data){
			r->next=p;
			p=p->next;
			r=r->next;
		}
		else{
			r->next=q;
			q=q->next;
			r=r->next;
		}
	}
	if(p!=NULL) r->next=p;    //将p剩余元素连接在新链表中
	if(q!=NULL) r->next=q;    //同上句
}

3.4 查找结点是否存在

/**
查找链表（带头结点）中是否存在一个值为x的结点，存在，则删除返回1，否则返回0
*/
int findAndDelete(LNode *C,int x){
	LNode *p,*q;
	p=C;
	while(p->next!=NULL){
		if(p->next->data==x)
			break;
		p=p->next;
	}
	if(p->next==NULL)    //查找结束
		return 0;
	else{
		/*删除部分*/
		q=p->next;
		p->next=p->next->next;
		free(q);
		return 1;
	}
	
}