[数据结构与算法]顺序表链表双向链表循环链表等操作

一些考研的顺序表，链表，循环列表，双向链表的操作；晚点打栈队列那些，有需要可以关注一下。
自行复制吧，自己敲的，只能说可能存在健壮性的问题。有意见欢迎指出，但是是应试考试，所以太细节的就没扣。

顺序表

代码如下：

#define Initsize 50
typedef struct {
	int *data;
	int length;
}sqlist;



sqlist Initlist(sqlist &l) {
	l.data = new int[Initsize];
	if (!l.data) {
		cout << "申请失败" << endl; exit(0);}
	l.length = 0;
	return l;
}//初始化

int Isempty(sqlist l) {
	if (l.length == NULL) { return 1; }
	else return 0;//判定空
}

sqlist Assignment(sqlist &l) {
	int i;
	for (i = 0; i < 10; i++) {
		l.data[i] = i + 1;
		l.length++;
	}
	return  l;
}

sqlist Export(sqlist l) {
	cout << "表中的数据是" << endl;
	int i ;
	for (i = 0; i < l.length; i++) {
		cout << l.data[i] <<' ';
		
	}
	cout << endl;
	cout << "----------------------------------";
	cout << endl;
	return l;
}

bool Listinsert(sqlist &l, int i,int e) {
	if (i<1 || i>l.length + 1) { cout << "no change"<<endl;   return false; }
	if (l.length >= Initsize) { cout << "no change" << endl;    return false; }
	for (int j = l.length; j >= i; j--) {
		l.data[j] = l.data[j - 1];
	}
	l.data[i-1] = e;
	l.length++;
	
	return true;
	
}

int Listdelete(sqlist &l, int i, int &e) {
	if (i<1 || i>l.length) { cout << "not legality" << endl; e = NULL; return false; }
	e = l.data[i - 1];
	for (int j = i; j < l.length;j++) {
		l.data[j - 1] = l.data[j];
	}
	l.length--;
	return e;
}
int findi(sqlist l, int i) {
	cin >> i;
	if (i<1 || i>l.length) { return false; }
	cout << "您查找的是" <<i<<"位置"<< endl;
	return l.data[i - 1];
}

int main() {
	sqlist a;
	int b,d;
	a = Initlist(a);
	a = Assignment(a);
	Export(a);
	/*cout << "你要在什么位置插入？:";
	cin >> b;
	cout << "你要插入什么数？:";
	cin >> d;*/
	Listinsert(a, 100, 1);
	Export(a);
	Listdelete(a, 1, b);
	Export(a);
	cout << b << endl;
	d=findi(a,5);
	cout << d << endl;
	system("pause");
}

链表

代码如下（）：

typedef struct Lnode {
	int data;
	struct Lnode *next;
}Lnode,*Linklist;

void Initlist(Linklist &L) {
	L = new Lnode;
	L->next = NULL;
}//初始化一个线性表，我们在主函数里可以通过L = new Lnode;L->next = NULL;初始化，也可以通过initlist（L）；初试话一个L表

int Listempty(Linklist L) {
	if (L->next = NULL) { return 0; }
	else return 1 ;
}//判定表是否为空。

int DestroyList(Linklist &l) {
	Lnode*p;
	while(l) {
		p = l;
		l = l ->next;
		delete p;
	}//销毁一个表，注意，当表销毁后不能exportall输出，会导致内存访问冲突，我不是很懂，也懒得解决。
	return 1;
}

int ListLength_l(Linklist L) {
	Linklist p;
	int i;
	p = L->next;//首元结点的地址就在L->next里
	i = 0;
	while (p != NULL) {
		i++;
		p = p->next;
	}
	return i;//求表长；
}

void Exportall(Linklist l) {
	
		Lnode *q;
		q = l->next;
		int a = ListLength_l(l), b;
		cout << "now , this is the linklist:" << endl;
		for (b = 1; b <= a; b++) {
			cout << q->data << " ";
			if (q->next) { q = q->next; }
		}
		cout << endl;
	//顺序输出所有元素；
}
void Createlist_h(Linklist &l,int a) {
	Lnode* p;
	l = new Lnode;
	l->next = NULL; 
	cout << "the element:"<<endl;
	for (int i = 1; i <= a; i++) {
		p = new Lnode;
		cin >> p->data;
		p->next = l->next;
		l->next = p;
		}
	Exportall(l);//头插法
}

void Listinsert(Linklist &l, int i, int e) {
	Lnode *p; int j;
	if (i < 1) { exit(0); cout << "no legallocation." << endl; }
	p = l; j = 0;
	while (p&&j < i-1 ) {
		p = p->next;
		j++;
	}//指定位置插入元素
	Lnode *s;
	s = new Lnode;
	s->data = e;
	s->next = p->next;
	p->next=s;
	Exportall(l);
}

int LocateElem_L(Linklist L, int e) {
	Lnode *p = L->next;
	int i = 1;
	while(p != NULL && p->data != e) {
		p = p->next;
		i++;
	}//定位指定位置元素
	if(p) return i;
	else { cout << "no vaild element" << endl; return 0; };
}

void LinklistDeleteelem(Linklist &l, int i, int &e) {
	Lnode *p = l; int j = 0; Lnode *q;
	while (p&&j < i - 1) {
		p = p->next; j++;
	}
	q = p->next;
	p->next = q->next;
	delete q;
	Exportall(l);//删除指定位数元素
}

void CreateList_r(Linklist &l, int i) {
	Lnode* p;
	Lnode* r;
	l = new Lnode;
	l->next = NULL;
	r = l;
	cout << "the element:" << endl;
	for (int b = 1; b <= i; b++) {
		p = new Lnode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}//尾插法
	Exportall(l);
}



int main() {
	int i ;
	Linklist L;
	int b;
	Initlist(L);//初始化单链表；
	//Createlist_h(L, 5);//创建一个含元素的链表；
	CreateList_r(L, 5);//尾插法；
	Listinsert(L, 6, 20);//在第i个结点前插入值为e的新节点；
	i=LocateElem_L(L, 5);
	cout << i << endl;//查找值为e的元素；
	LinklistDeleteelem(L, 5, b);
	b=ListLength_l(L);
	cout << b << endl;
	system("pause");
}

循环链表

typedef struct Lnode {
	int data;
	struct Lnode *next;
}Lnode,*Linklist;

void Initlist_r(Linklist &l) {
	l = new Lnode;
	l->next = l;//循环列表；
}
int Listempty_r(Linklist l) {
		if (l->next = l) { return 0; }
		else return 1 ;
	}//判定表是否为空。

int ListLength_l(Linklist L) {
		Linklist p;
		int i;
		p = L->next;//首元结点的地址就在L->next里
		i = 0;
		while (p != L) {
			i++;
			p = p->next;
		}
		return i;//求表长；
	}

void Exportall(Linklist l) {
	
		Lnode *q;
		q = l->next;
		int a = ListLength_l(l), b;
		cout << "now , this is the linklist:" << endl;
		for (b = 1; b <= a; b++) {
			cout << q->data << " ";
			if (q->next!=l) { q = q->next; }
		}
		cout << endl;
	顺序输出所有元素；
}
void Createlist_r(Linklist &l, int i) {
	Lnode *r; 
	Lnode *p;
	r = l; int j = 0;
	if (!l || i < 1)exit(0);
	for (j = 0; j < i; j++) {
		p = new Lnode;
		cin >> p->data;
		p->next = l;
		r->next = p;
		r = p;
	}
}

int main() {
	Linklist L;
	Initlist_r(L);
	Createlist_r(L, 5);
	Exportall(L);
	system("pause");
}

双向链表

//双向链表
typedef struct DLnode{
	int data;
	struct DLnode *prior, *next;

}DLnode, *DLinklist;

int DInitlist(DLinklist &l) {
	l = new DLnode;
	l->prior = l;
	l->next = l;
	l->data = NULL;
	return 1;//初始化
}

int Dlistlength(DLinklist l) {
	int i=0;
	DLnode *p ;
	p = l;
	while (p->next != l) {
		p = p ->next;
		i++;
	}
	return i;//返回表长，特别的，当l不存在或为空返回0；
}

int  ExportAll(DLinklist l) {
	int i = 1; 
	if (Dlistlength(l) < 1) { cout << "not vaild length" << endl; return 0; }
	DLnode *p;
	p = l -> next;
	for (i = 1; i <= Dlistlength(l); i++) {
		cout << p->data << " ";
		p = p->next;//遍历输出所有元素；
	}
}

int DCreateList(DLinklist &l,int i) {
	DLnode *p, *r;
	if (i < 1) {
		cout << "not vaild" << endl; return 0;
	}
	else {
		r = l;
		int j = 1;
		for (j = 1; j <= i; j++) {
			p = new DLnode;
			p->data = j + 5;
			p->prior = r;
			p->next = l;
			r->next = p;
			r = p;
		}
		//尾插建立双向链表；
		return 1;
	}
}
int Dlocal(DLinklist l,int i) {
	DLnode*p; int j = 1;
	p = l;
	for (j = 1; j <= i;j++) {
		p = p->next;
	}//定位第i个元素的值
	return p->data;

}
void Dlistinsert(DLinklist &l, int i, int a) {
	DLnode * p; p = l;
	DLnode * s;
	int j;
	if (i<1 || i>Dlistlength(l)+1) { cout << "not vaild localtion" << endl; }//注意，我们可以插在队尾
	else	//注意这个循环和定位第i元素不一样，我们要使p在s前一个节点；
		for (j = 1; j < i; j++) {
			p = p->next;
		}
		s = new DLnode;
		s->data= a;
		s->next = p->next;
		p->next->prior = s;
		s->prior = p;
		p->next = s;
		
}

int main() {
	DLinklist L;
	DInitlist(L);
	DCreateList(L,10);
	ExportAll(L);
	cout << endl;
	Dlocal(L, 2);
	cout << endl;
	Dlistinsert(L ,11, 5);
	ExportAll(L);
	cout << endl;
	cout << Dlistlength(L) << endl;
	system("pause");
}