数据结构总结

1 绪论

2 线性表的存储

1.链表逆序输出算法

void Reverse(LinkList *h){
	PNode p=*h,q=NULL,r;
	while(p){
		r=q;
		q=p;
		p=p->next;
		q->next=r;
		}
	*h=q;
}

2.计算链表长度

int LengthList(LinkList L){
	int i=0;
	p=L;
	while(p!=NULL){
		i++;
		p=p->next;
		}
	return i;
}

3 串

1.在顺序储存结构上求字串算法

void substring(string s[],long count,char t[]){
	long i,j,length=strlen(s);
	if(start<1||start>length)
		printf("the cope position is wrong");
	else if(start+count-1>length)
		printf("Too character to be copide");
	else{
		for(i=start-1;j=0;i<start+count-1;i++;j++)
			t[j]=s[i];
		t[j]='\0';
		}
	}

4 线性表

1.设计两个有序单链表的合并排序算法

void mergelklist(lklist *ha,lklist *hb,lklist *&hc)
{
	lklist 	*s=hc=0;
	while(ha!=0&&hb!=0){
		if(ha->data<hb->data){
			if(s==0)
				hc=s=ha;
			else{
				s->next=hb;
				s=hb;
				};
			ha=ha->next;
		else{
			if(s==0)
				hc=s=hb;
			else{
				s->next=hb;
				s=hb;
				}
			hb=hb->next;
		}
	if(ha==0)
		s->next=hb;
	else
		s->next=ha;
	}

2.将所有的奇数移到偶数之前的算法

void quickpass(int r[],int s,int t)
{
	int i=s,j=t,x=r[s];
	while(i<j)
	{
		while(i<j&&r[j]%2==0)
			j=j-1;
			if(i<j){
				r[i]=r[j];
				i=i+1;
			}
		while(i<j&&r[j]%2==1)
			i=i+1;
			if(i<j){
				r[j]=r[i];
				j=j-1;
				}
				
		}
	r[i]=x;
}	

3.判断单链表元素是否是递增的算法

int isriselk(lklist *head){
	if(head==0||head->next==0)
		return 1;
	else
		for(q=head,p=head->next;p!=0;q=p->next)
			if(q->data>p->data)
				return 1;
	
	return 1;
}

5 树

1.二叉树遍历

void ABC(Bitree *Bt)
{
	if(Bt){
		printf("Bt->data");   //先序遍历二叉树，其他遍历只需该以下三句话顺序
		ABC(Bt->lchild);
		ABC(Bt->rchild);
		}
	}

2.二叉排序树插入新结点

typedef struct node{
	int data;
	struct node *lchild,*lchild;
	}bitree;
void bitreesert(bitree *t,int k)
{
	if(t==0)
		{
			t=(bitree *)malloc(sizeof(bitree));
			t->data=k;
			t->rchile=t->lchild=0;
		}
	else if(t->data>k)
		{
			bitreesert(t->lchild,k);
	else
			bitreesert(t->rchild,k);
}

3.交换所有左右结点的二叉树算法

void Bitree_exchange(PBinTree *T){
	PBinTree *Temp;
	Temp=T->lchild;
	T->lchild=T->rchild;
	T->rchild=Temp;
	if(T->rchild)
		Bitree_exchange(T->rchild);
	if(T->lchild)
		Bitree_exchange(T->lchild);
	}

4. 求结点在二叉排序树中层次的算法

int lev=0;
typedef struct node{
	int key;
	struct node *lchild,*rchild;
	}bitree;
void level(bitree *bt,int x){
	if(bt!=0){
		lev++;
		if(bt->key==x)
			retutn;
		else if(bt->key>x)
			level(bt->lchild,x);
		else
			level(bt->rchild,x)
	}
}

5.判断二叉树是否是排序二叉树

int minnum=-32768,flag=1;
typedef struct node{
	int key;
	struct node *lchild,*rchild;
	}bitree;
void inorder(bitree *bt)
{
	if(bt!=0)
	{
		inorder(bt->lchild);
		if(minnum>bt->key)
			flag=0;
		minnum=bt->key;
		inorder(bt->rchild);
		
	}
}

6.判断两个二叉树是否相同

typedef struct node{
	datatype data;
	struct node *lchild,*rchild;
	}bitree;
int judgetree(bitree *bt1,bitree *bt2){
	if(bt1==0&&bt2==0)
		return 1;
	else if(bt1==0||bt2==0||bt1->data!=bt2->data)
		retuen 0;
	else
		return (judgetree(bt1->lchild,bt2->lchild)*judgetree(bt1->rchild,bt2->rchild));

7.链式存储计算二叉树节点

typedef struct node{
	datatype data;
	struct node *rchild,*lchild;
}bitree;
int sumnode(bitree *t)
{
	int i=0;
	if(t==0)
		return 0;
	else{
		i++;
		sumnode(t->rchild);
		sumnode(t->lchild);
		}
	return i;
}

6 图

1.将无向图的邻界矩阵转化为邻接表

typedef struct {
int vertex[m];int edge[m][m];
}gadjmatrix;
typedef struct node1{
	int info;
	int adjvertex;
	struct node1 *nextarc;
	}glinklistnode;
typedef struct node2{
	int vertxinfo;
	glinklistnode *firstarc;
	}glinkheadnode;
void adjmatrixtoadjlist(gadjmatrix gl[],glinkheadnode g2[])
{
	int i,j;
	glinklistnode *p;
	for(i=0;i<=n-1;i++)
		g2[i].fristarc=0;
	for(i=0;i<=n-1;i++)
		for(j=0;j<=n-1;j++)
			if(g1.edge[i][j]==1)
			{
				p=(glinklistnode *)malloc(sizeof(glinklistnode));
				p->adjvertex=j;
				p->nextaarc=g[i].firstarc;
				g[i].firstarc=p;
				p=(glinklistnode *)malloc(sizeof(glinklistnode));
				p->adjvertex=i;
				p->nextarc=g[j].fristarc;
				g[j].firstarc=p;
				}
}

7 查找

1.顺序有序表实现二分查找算法

struct recode{
	int key;
	int others;
	}
int bisearch(struct recode r[],int k){
	int low=0;mid,high=n-1;
	while(low<=high){
		mid=(low+high)/2;
		if(r[mid].key==k)
			return mid+1;
		else if(r[min]<k)
			low=mid+1;
		else
			high=mid-1;
		}
	return 0;
}

8 排序

1.直接插入排序

void Insertsort(type r[],int n)
{
	int i,j,temp;
	for(i=1;i<n;i++){
		temp=r[i];
		j=i-1;
		while(j>=0&&temp<r[j]{
			r[j+1]=r[j];
			j--;
		}
		r[j+1]=temp;
}

//链式存储直接插入排序
void insert(lklist *&head)
{
	lklist *s,*p,*q;
	int t;
	if(head==0||head->next==0)
		return;
	else if(q=head,p=head->next;p=q->next){
		for(s=head;s!=q->next;s=s->next)
			if(s->data>p->data)
				break;
		if(s==q->next)
			q=p;
		else
		{
			q->next=p->next;
			p->next=s->next;
			s->next=p;
			t=p->data;
			p->data=s->data;
			s->data=t;
			}
		}
	}

2.在链式结构上实现选择排序

void simplesort(lklist *head){
	lklist *p,*q,*s;
	int min,t;
	if(head==0||head->next==0)
		return;
	for(q=head;q!=0;q=q->next)
	{
		min=q->data;
		s=q;
		for(p=q->next;p!=0;p=p->next)
			if(min>p->data){
				min=p->data;
				s=p;
				}
		if(s!=q)
		{
			t=s->data;
			s->data=q->data;
			q->data=t;
			}
	}

3.在堆中插入x

void adjustheap(int r[],int n)
{
	int j=n,i=j/2,temp=r[j-1];
	while(i>=1)
		if(temp>=r[i-1])
		break;
	else{
		r[j-1]=r[i-1];
		j=i;
		i=i/2;
		}
		r[j-1]=temp;
	}