严蔚敏版数据结构所有算法代码

严蔚敏版数据结构所有算法代码

------------------------线性数据结构-----------------------------

2013年9月//线性表、链表

//栈、队列

//数组、广义表

//串

-------------------------线性表----------------------

typedef struct

{

char name[20];//注意如果应用指针的形式

//在初始化每个结点时一定要先为结点中的每个变量开辟内存空间

char sex;

char addr[100];

unsigned int age;

char phonenum[20];

}node;//结点描述

typedef struct

{

node *p;

int length;//当前顺序表长度

int listsize;//当前分配的线性表长度

}list;//线性表描述

list L;//定义一个线性表

int initlist(list &l)//构造一个空的线性表

{

l.p=(node*)malloc(LIST_INIT_SIZE*sizeof(node));

if(!(l.p))

exit(1);

l.length=0;

l.listsize=LIST_INIT_SIZE;

return true;

}

void destroylist(list &l)//销毁线性表操作

{

if(l.p!=NULL)

{

free(l.p);

printf("销毁成功!\n");

}

else

1

printf("线性表不存在！\n");

}

int clearlist(list &l)//将线性表置空操作

{

if(l.p==NULL)

{

printf("线性表不存在！\n");

return false;

}

else

{

free(l.p);

l.p=(node*)malloc(l.listsize*sizeof(node));

l.length=0;

}

return true;

}

int listempty(list &l)//判断线性表是否为空表

{

if(l.p==NULL)

return true;

else

return false;

}

int getelem(list &l,int i,node &e)//用e返回表中第i个数据元素

{

if(l.p==NULL)

return false;

else

e=l.p[i-1];

return true;

}

int priorelem(list &l,int i,node &pre_e)//得到第i个元素的前驱元素{

if(i==0||l.p==NULL)

return false;

else

pre_e=l.p[i-1];

return true;

}

int nextelem(list &l,int i,node &next_e)//得到表中第i个元素的后继元素{

if(i>=l.length||l.p==NULL)

return false;

2

else

next_e=l.p[i+1];

return true;

}

int insertlist(list &l,int i,node &e)//将元素e插入到表l中第i个元素的后面

{

node *q,*k;

if(i<1||i>l.length+1)

return false;

if(l.length>=l.listsize)

{

l.p=(node

*)realloc(l.p,(l.listsize+LISTINCREMENT)*sizeof(node));

if(!l.p)

exit(1);

l.listsize+=LISTINCREMENT;

}

k=&l.p[i-1];

for(q=&l.p[l.length-1];q>k;q--)

*(q+1)=*q;

*k=e;

l.length++;

return true;

}

int deletelist(list &l,int i,node &e)//删除表中第i个元素并用e返回其值

{

node *q;

int j=i-1;

if(i<1||i>l.length)

return false;

e=l.p[i-1];

for(q=&l.p[i-1];j

*q=*(++q);

l.length--;

return true;

}

void mergerlist(list la,list lb,list &lc)//归并两个按非递减排列的线性表

{

int la_len,lb_len,i=1,j=1,k=0;

node ai,bj;

la_len=la.length;

3

lb_len=lb.length;

while(i<=la_len&&j<=lb_len)

{

getelem(la,i,ai);

getelem(lb,j,bj);

if(ai.a<=bj.a)

{

insertlist(lc,++k,ai);

i++;

}

else

{

insertlist(lc,++k,bj);

j++;

}

}

while(i<=la_len)

{

getelem(la,i,ai);

insertlist(lc,++k,ai);

i++;

}

while(j<=lb_len)

{

getelem(lb,j,bj);

insertlist(lc,++k,bj);

j++;

}

}

int ListAscendingOrder(list &l)//按结点中某一元素的比较升序排列线性表中的结点

{

node e;

int i,j;

if(l.p==NULL||l.length==1)

return ERROR;

for(i=0;i

for(j=i+1;j

if(l.p[i].num>=l.p[j].num)

{

e=l.p[i];

l.p[i]=l.p[j];

l.p[j]=e;

}

4

return OK;

}//省略降序排列

void MergerList(list la,list lb,list &lc)//将两线性表升序排列后再归并{

node *q,*k,e1;

int i=0,j=0,m=0,n;

ListAscendingOrder(la);

ListAscendingOrder(lb);

printf("表a升序排列后为：\n");

for(i=0;i

printf("%d ",la.p[i].num);

printf("\n");

printf("表b升序排列后为：\n");

for(i=0;i

printf("%d ",lb.p[i].num);

printf("\n");

i=0;

while(i

{

if(la.p[i].num<=lb.p[j].num)

{

e1=la.p[i];

i++;

}

else

{

e1=lb.p[j];

j++;

}

if(e1.num!=lc.p[lc.length-1].num)

InsertList(lc,++m,e1);

}

if(i

while(i

{

if(la.p[i].num!=lc.p[lc.length-1].num)

InsertList(lc,++m,la.p[i]);

i++;

}

if(j

while(j

{

if(lb.p[j].num!=lc.p[lc.length-1].num)

InsertList(lc,++m,lb.p[j]);

5

j++;

}

printf("按升序排列再归并两表为：\n");

for(n=0;n

printf("%d ",lc.p[n].num);

printf("\n");

}

----------------------链表----------------------------- typedef struct

{

int num;

}node;

typedef struct LIST

{

node data;

struct LIST *next;

}list,*slist;

int CreatList(slist &head)//此处应为只针对的引用

{

head=(list *)malloc(sizeof(list));

if(!head)

return ERROR;

head->next=NULL;

return OK;

}

void InvertedList(slist &head1,slist &head2)

{//构造新表逆置单链表函数

list *p,*q;

p=head1->next;

q=p->next;

if(p==NULL)

printf("链表为空无法实现逆置操作\n");

else

{

while(q!=NULL)

{

p->next=head2->next;

head2->next=p;

p=q;

q=q->next;

}

p->next=head2->next;

head2->next=p;

printf("逆置成功！?\n");

6

}

}

void InsertList(slist &head,node &e)//此处应为指针的引用{//而不应该是list *head

list *p,*q;

p=(list *)malloc(sizeof(list));

q=head;

while(q->next!=NULL)

q=q->next;

p->next=q->next;

q->next=p;

p->data=e;

}

void InvertedList(sqlist &head)

{//-------不构造新表逆置单链表函数---------// list *p,*q,*k;

p=head->next;

q=p->next;

k=q->next;

p->next=NULL;

while(k!=NULL)

{

q->next=p;

p=q;

q=k;

k=k->next;

}

q->next=p;

head->next=q;

}

//----交换链表中第i个和第j个结点，函数实现如下——// int SwapListNode(sqlist &head,int i,int j)

{

int m,n,m1,n1,sum=0;

list *p,*q,*k,*c,*d,*ba;

ba=head->next;

while(ba!=NULL)

{

sum++;

ba=ba->next;

}

if(i==j||i>sum||j>sum||i<1||j<1)

{

printf("所要交换的两个结点有误！\n");

7

return ERROR;

}

if(i

{ m=i; n=j;}

else

{ m=j;n=i;}

p=head;q=head;

for(m1=1;m1<=m;m1++)

p=p->next;

for(n1=1;n1<=n;n1++)

q=q->next;

if(p->next==q)

{//如果结点相邻

k=head;

while(k->next!=p)

k=k->next;

//相邻两结点的交换

p->next=q->next;

q->next=p;

k->next=q;

}

else

{//如果结点不相邻

k=head;c=head;

while(k->next!=p)

k=k->next;

while(c->next!=q)

c=c->next;

d=p->next;

//不相邻两结点之间的交换

p->next=q->next;

c->next=p;

k->next=q;

q->next=d;

}

return OK;

}

//-----将链表中结点按结点中某一项大小升序排列，函数实现如下-----// int AscendingList(sqlist &head)

{

int m,n,sum=0,i,j;

list *p,*q,*k;

k=head->next;

while(k!=NULL)

8

{

sum++;

k=k->next;

}

for(i=1;i

for(j=i+1;j<=sum;j++)

{

p=head->next;

m=1;

while(m!=i)

{

m++;

p=p->next;

}

q=head->next;

n=1;

while(n!=j)

{

n++;

q=q->next;

}

if(p->data.exp>q->data.exp)//如果按exp降序排列，则应将>改为<；

SwapListNode(head,i,j);

}

return OK;

}

//-----将两链表合并为一个链表------//

int AddList(sqlist &head1,sqlist &head2,sqlist &head3)

{//已将表head1和表head2按某一项升序排列过

sqlist p,q;

node e;

p=head1->next;

q=head2->next;

while(p!=NULL&&q!=NULL)

{

if(p->data.expdata.exp)

{

InsertList(head3,p->data);

p=p->next;

}

else

if(p->data.exp>q->data.exp)

{

9

InsertList(head3,q->data);

q=q->next;

}

else

if(p->data.exp==q->data.exp)

{

e.coefficient=p->data.coefficient+q->data.coefficient;

e.exp=p->data.exp;//e.exp=q->data.exp;

InsertList(head3,e);

p=p->next;

q=q->next;

}

}

if(p!=NULL)

while(p!=NULL)

{

InsertList(head3,p->data);

p=p->next;

}//如果p中有剩余，则直接将p中剩余元素插入head3中if(q!=NULL)

while(q!=NULL)

{

InsertList(head3,q->data);

q=q->next;

}//如果q中有剩余，则直接将q中的剩余元素插入head3中

return 0;

}

-----------------------栈------------------------------

//---------利用栈结构实现数制之间的转换------书3.2.1//

typedef struct

{

int num;

}node;

typedef struct

{

node *base;

node *top;

int stacksize;

}stack;//顺序栈结构定义

int CreatStack(stack &stackll)

{

stackll.base=(node *)malloc(INITSTACKSIZE*sizeof(node));

if(!stackll.base)

exit(OVERFLOW);

10

stackll.top=stackll.base;

stackll.stacksize=INITSTACKSIZE;

return OK;

}

void push(stack &s,node e)

{//进栈操作

if(s.top-s.base>=s.stacksize)

{ s.base=(node

*)realloc(s.base,(s.stacksize+INCRESTACKMENT)*sizeof(node));

if(!s.base)

exit(OVERFLOW);

s.top=s.base+s.stacksize;//可以不写此语句；

s.stacksize+=INCRESTACKMENT;

}

*(s.top++)=e;//*s.top++=e;

}

void pop(stack &s,node &e)

{//出栈操作

if(s.top==s.base||s.base==NULL)

printf("信息有误！\n");

else

e=*--s.top;

}

//-------取栈顶元素函数------//

void gettop(stack &s,node &e)

{

if(s.base==s.top)

printf("栈为空，无法取得栈顶元素！\n");

else

{

e=*(s.top-1);

}

}

//-----栈的应用：括号匹配的检验------书3.2.2//

//省略了大部分上述已有代码//

int zypd(char c)

{//判断是否为左括号字符

if(c=='['||c=='{'||c=='(')

return OK;

else

return ERROR;

}

int main(void)

{

11

stack s;

node e1,e2,e3;

char st[INITSTACKSIZE];

int i=0,j;

CreatStack(s);

printf("请输入括号字符，以'#'做结束符：");

scanf("%c",&st[i]);

while(st[i]!='#')

{

i++;

scanf("%c",&st[i]);

}

if(!zypd(st[0]))

printf("输入字符不合法！\n");

else

{

for(j=0;j

{

if(zypd(st[j]))

{//如果是左括号则将此字符压入栈中

e1.c=st[j];

push(s,e1);

}

else

{//如果当前st[j]元素不是左括号

//则取出栈顶元素，比较栈顶元素与当前st[j]元素是否项匹配

//如果匹配，则栈顶元素出栈

gettop(s,e2);

if(e2.c=='['&&st[j]==']'||e2.c=='{'&&st[j]=='}'||e2.c=='('&&st[j] ==')')

pop(s,e3);

else

{

printf("括号验证失败！\n");

break;

}

}

}

if(s.top==s.base)//当循环结束时，如果栈为空栈说明输入的括号合法printf("括号验证成功！\n");

}

getchar();

system("pause");

12

return 0;

}

//----------链栈描述---------//

typedef struct Node

{

int num;

struct Node *next;

}node;

typedef struct

{

Node *top;

Node *base;

}stack;

void InitStack(stack &s)

{

s.base=(Node *)malloc(sizeof(node));

if(!s.base)

exit(1);

else

{

s.base->next=NULL;

s.top=s.base;

}

}

void InsertStack(stack &s,node e)

{

node *p;

p=(node *)malloc(sizeof(node));

if(!p)

exit(1);

else

{

*p=e;

p->next=s.top;

s.top=p;

}

}

void DeleteStack(stack &s,node &e)

{

node *p;

if(s.top==s.base)

printf("栈为空！\n");

else

{

13

p=s.top;

s.top=s.top->next;

e=*p;

free(p);

}

}

--------------------队列---------------------- //------链队列的描述及操作-------//

typedef struct Node

{

int a;

struct Node *next;

}Qnode,*QueuePtr;

typedef struct

{

QueuePtr front;

QueuePtr rear;

}LinkQueue;

void InitQueue(LinkQueue &Q)

{

Q.front=(Qnode *)malloc(sizeof(Qnode));

if(!Q.front)

exit(1);

Q.rear=Q.front;

Q.front->next=NULL;

}

void InsertQueue(LinkQueue &Q,Qnode e)

{

QueuePtr p;

p=(Qnode *)malloc(sizeof(Qnode));

if(!p)

exit(1);

*p=e;

p->next=NULL;

Q.rear->next=p;

Q.rear=p;

}

void DeleteQueue(LinkQueue &Q,Qnode &e)

{

Qnode *p;

if(Q.front==Q.rear)

printf("队列为空！\n");

else

{

14

p=Q.front->next;

e=*p;

Q.front->next=p->next;

if(p==Q.rear)

Q.rear=Q.front;

free(p);

}

}

//-------------循环队列---------------// typedef struct node

{

int data;

struct node *next;

}node;

typedef struct queue

{

node *base;

int front;

int rear;

}Queue;

int tag;

void InitQueue(Queue &Q)

{

Q.base=(node *)malloc(MAX*sizeof(node));

if(!Q.base)

exit(1);

Q.front=Q.rear=0;

tag=0;

}

void InsertQueue(Queue &Q,node e)

{

if(tag==1&&Q.front==Q.rear)

printf("循环队列已满！\n");

else

{

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAX;

if(Q.rear==Q.front)

tag=1;

}

}

void DeleteQueue(Queue &Q,node &e)

{

if(tag==0&&Q.front==Q.rear)

15

本文来源：https://www.bwwdw.com/article/ggke.html