数据结构（C）

基础知识

• 数据是所有能被输入计算机中，且能被计算机处理的符号的集合
• 数据元素是数据的基本单位
• 数据项是独立含义的数据最小单元
• 数据对象是独立含义最小单位
• 数据对象是指性质相同的数据元素的集合
• 数据结构是带结构的数据元素的集合
• 主要讨论数据之间的相邻关系或者邻接关系
• 顺序存储结构是采用一组连续的存储单元存放所有的数据元素
• 链式存储结构中，每个逻辑单元用一个内存单节点存储，每个节点是单独分配的，所有的节点地址不一定是连续的
• 抽象数据类型=逻辑结构+抽象运算
• 算法的5个特性
  • 有穷性
  • 确定性
  • 可行性
  • 0个或多个输入
  • 一个或者多个输出
• O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n3)<O(2^n)<O(n!)
• 线性表的三个特性：有穷性，一致性，序列性
• 链表的插入结点
  • s->next=p->next;
  • p->next=s;
• 链表的删除结点
  -p->next=p->next->next;
• 链表的初始化，创建头结点 L->next=NULL;
• 栈空的条件：s->top==-1;
• 栈满的条件：s->top==maxSize-1;
• 进栈e操作：top++;将e放在top处
• 退栈操作：从top处取出元素e;top–;
• 栈的初始化条件：s->top=-1;
• 和出栈运算相比，取栈顶元素没有移动栈顶指针
• 栈空条件，栈1空：top1=-1;栈2空：top2==MaxSize
• 栈满条件：top1==top2-1
• 元素x进栈操作，进栈1操作：top1++;data[top1]=x;进栈2操作：top2–;data[top2]=x;
• 出栈x操作，出栈1操作，x=data[top1];top1一；出栈2操作，x=data[top2];top2++;
• 链栈:栈空的条件：s->next==NULL;没有栈满的条件
• 元素e进栈的操作：新建一个结点存放元素e，将结点p插入头结点之后。
• 出栈的操作：取出首结点的data值并将其删除
• 队空的条件：q->front==q->rear
• 队满的条件：q->rear==maxsize-1
• 元素e进栈:rear++,data[rear]=e;
• 出队：front++;e=data[front];
• 链队：队空的条件：q->rear==NULL,队满不考虑
• 元素e进栈的操作：新建一个结点存放元素e，将结点p插入作为尾结点
• 出队的操作：取出队首结点的data值并将其删除

线性表

顺序表

顺序表类型定义

typedef struct
{   ElemType data[Maxsize];
    int length;
}SqList; //顺序表类型

其中data成员存放元素，length.成员存放线性表的实际长度。
说明：注意逻辑位序和物理位序相差1。

建立顺序表

void
CreateList(SqList &L,ElemType a[],int n)
{ int i=0,k=0;
   L=(SqList *)malloc(sizeof(SaList));
   while (i<n) //i扫描a中元素
   {  L->data[k]=a[i];
     k++;1++; //k记录插入到L中的元素个数
   }
    L->length=k；
}

初始化线性表

void InitList(SqList *&L)
{  L=(SqList *)malloc(sizeof(SqList));
　　　　//分配存放线性表的顺序表空间
   L->length=0;
}

销毁线性表

void DestroyList(SqList *&L)
{
    free(L);
}   

判断是否是空表

bool ListEmpty(SqList *L)
{
   return(L->length==0);
}

求线性表的长度

int ListLength(SqList *L)
{
     return(L->length);
}

输出线性表

void DispList(SqList *L)
{  int i;
   if (ListEmpty(L)) return;
   for (i=0;i<L->length;i++)
      printf("%c"，L->data[i]);
   printf("\n");
} 

求某个数据元素值

bool GetElem(SqList *L，int i，ElemType &e)
{     
   if (i<1 || i>L->length)  return false;
   e=L->data[i-1];
   return true;
}  

按元素值查找

int LocateElem(SqList *L，ElemType e)
{  int i=0;
   while (i<L->length && L->data[i]!=e)  
      i++;
   if (i>=L->length)  return 0;
   else  return i+1;
}

插入数据元素

bool  ListInsert(SqList *&L，int i，ElemType e)
{  int j;
   if (i<1 || i>L->length+1)
      return false;		//参数错误时返回false
   i--;				//将顺序表逻辑序号转化为物理序号
   for (j=L->length;j>i;j--)	//将data[i..n]元素后移一个位置
	L->data[j]=L->data[j-1];
   L->data[i]=e;		//插入元素e
   L->length++;		//顺序表长度增1
   return true;		//成功插入返回true
}

删除数据元素

bool ListDelete(SqList *&L，int i，ElemType &e)
{  int j;
   if (i<1 || i>L->length)	　	//参数错误时返回false
      return false;
   i--;					//将顺序表逻辑序号转化为物理序号
   e=L->data[i];
   for (j=i;j<L->length-1;j++)  	//将data[i..n-1]元素前移
	L->data[j]=L->data[j+1];
   L->length--;			//顺序表长度减1
   return true;			//成功删除返回true
}

删除线性表所有值为X的数据元素

void delnode1(SqList *&L， ElemType x)
{  int k=0， i;		//k记录值不等于x的元素个数
   for (i=0;i<L->length;i++)
      if (L->data[i]!=x)    	//若当前元素不为x，将其插入A中
      {   L->data[k]=L->data[i];
          k++;		 	//不等于x的元素增1
      }
   L->length=k;		//顺序表L的长度等于k
}

小前大后

以第一个元素为分界线（基准），将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。

void move1(SqList *&L)
{  int i=0， j=L->length-1;
   ElemType base=L->data[0];	//以data[0]为基准
   while (i<j)
   {  while (i<j && L->data[j]>base)
	 j--;	  	 	//从后向前扫描，找一个≤base的元素
      while (i<j && L->data[i]<=base)
	 i++;			//从前向后扫描，找一个>base的元素
      if (i<j)
        swap(L->data[i],L->data[j]);
   }
   swap(L->data[0],L->data[i]);
}

将L所有奇数移动到偶数的前面

void move1(SqList *&L)
{  int i=0,j=L->length-1;
   while (i<j)
   {  while (i<j && L->data[j]%2==0)
	 j--;			       //从右向左,找一个奇数元素
      while (i<j && L->data[i]%2==1)
        i++;			       //从左向右,找一个偶数元素
      if (i<j)			//若i<j，L->data[i]和L->data[j]交换
         swap(L->data[i],L->data[j]); 
   }
}

链表

单链表

单链表中结点类型定义:

typedef struct LNode      //定义单链表结点类型
{  ElemType data;
   struct LNode *next;    //指向后继结点
}  LinkNode;

头插法建表

void CreateListF(LinkNode *&L，ElemType a[]，int n)
{  LinkNode *s;
   int i;
   L=(LinkNode *)malloc(sizeof(LinkNode));
   L->next=NULL;		//创建头结点，其next域置为NULL
  for (i=0;i<n;i++)		//循环建立数据结点
  {  s=(LinkNode *)malloc(sizeof(LinkNode));
     s->data=a[i];		//创建数据结点s
     s->next=L->next;		//将s插在原开始结点之前，头结点之后
     L->next=s;
  }
}

尾插法建表

void CreateListR(LinkNode *&L，ElemType a[]，int n)
{  LinkNode *s，*r;
   int i;
   L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
   r=L;				//r始终指向尾结点，开始时指向头结点   
   for (i=0;i<n;i++)		//循环建立数据结点
   {	s=(LinkNode *)malloc(sizeof(LinkNode));
	s->data=a[i];		//创建数据结点s
	r->next=s;		//将s插入r之后
	r=s;
   }
   r->next=NULL;		//尾结点next域置为NULL
}

初始化线性表

void InitList(LinkNode *&L)
 {
    L=(LinkNode *)malloc(sizeof(LinkNode));    //创建头结点
    L->next=NULL;
 }

销毁线性表

void DestroyList(LinkNode *&L)
{   
   LinkNode *pre=L， *p=L->next;    //pre指向p的前驱结点
   while (p!=NULL)	//扫描单链表L
   {  free(pre);	//释放pre结点
      pre=p;		//pre、p同步后移一个结点
      p=pre->next;
   }
   free(pre);         //循环结束时，p为NULL，pre指向尾结点，释放它
}

判断线性表是否是空表

bool ListEmpty(LinkNode *L)
{
　　return(L->next==NULL);
}

求线性表的长度

int ListLength(LinkNode *L)
{
  　int n=0;
　  LinkNode *p=L;	//p指向头结点，n置为0（即头结点的序号为0）
       while (p->next!=NULL)
   {	n++;
	p=p->next;
   }
   return(n);		//循环结束，p指向尾结点，其序号n为结点个数
}

输出线性表

void DispList(LinkNode *L)
{
   LinkNode *p=L->next;	//p指向开始结点
   while (p!=NULL)		//p不为NULL，输出p结点的data域
   {  printf("%d "，p->data);
      p=p->next;		//p移向下一个结点
   }
   printf("\n");
}

求线性表L中位置i的数据元素

bool GetElem(LinkNode *L，int i，ElemType &e)
{  
   int j=0;
   LinkNode *p=L;	 //p指向头结点，j置为0（即头结点的序号为0）

   while (j<i && p!=NULL)
   {	j++;
	p=p->next;
   }

   if (p==NULL)	//不存在第i个数据结点，返回false
      return false;
   else			//存在第i个数据结点，返回true
   {  e=p->data;
      return true;
   }
}

按元素值查找

int LocateElem(LinkNode *L，ElemType e)
{
   int i=1;
   LinkNode *p=L->next;	//p指向开始结点，i置为1  

   while (p!=NULL && p->data!=e) 
   {  p=p->next;  		//查找data值为e的结点，其序号为i
      i++;
   }
     if (p==NULL)	//不存在元素值为e的结点，返回0
      return 0;
   else			//存在元素值为e的结点，返回其逻辑序号i
      return i;
}
   

插入数据元素

bool ListInsert(LinkNode *&L，int i，ElemType e)
{  int j=0;
   LinkNode *p=L，*s;          	//p指向头结点，j置为0

   while (j<i-1 && p!=NULL)
   {	j++;
	p=p->next;
   }

   if (p==NULL)		//未找到第i-1个结点，返回false
       return false;
   else				//找到第i-1个结点p，插入并返回true
   {
	s=(LinkNode *)malloc(sizeof(LinkNode));
	s->data=e;		//创建新结点s，其data域置为e
	s->next=p->next;	//将s插入到p之后
	p->next=s;
	return true;
   }
}

删除数据元素

bool ListDelete(LinkNode *&L，int i，ElemType &e)
{  int j=0;
   LinkNode *p=L，*q;		//p指向头结点，j置为0

   while (j<i-1 && p!=NULL)	//查找第i-1个结点
   {	j++;
	p=p->next;
   }
   if (p==NULL)		//未找到第i-1个结点，返回false
	return false;
   else				//找到第i-1个结点p
   {	q=p->next;		//q指向第i个结点
	if (q==NULL)		//若不存在第i个结点，返回false
	   return false;
	e=q->data;
	p->next=q->next;	//从单链表中删除q结点
	free(q);		//释放q结点
	return true;		//返回true表示成功删除第i个结点
   }
}

带头结点的单链表逆置

void  Reverse(LinkNode *&L)
{ 
   LinkNode *p=L->next，*q;
   L->next=NULL;
     while  (p!=NULL)
   {   q=p->next;		//临时保存p的后继结点
       p->next=L->next;	//将p结点采用头插法连接
       L->next=p;
       p=q;
   }
}
     

将L其拆分成两个带头结点的单链表L1和L2

void split(LinkNode *&L，LinkNode *&L1，LinkNode *&L2)
{  LinkNode *p=L->next，*q，*r1;		//p指向第1个数据结点
   L1=L;					//L1利用原来L的头结点
   r1=L1;					//r1始终指向L1的尾结点
   L2=(LinkNode *)malloc(sizeof(LinkNode));	//创建L2的头结点
   L2->next=NULL;				//置L2的指针域为NULL      
   while (p!=NULL)
   {	r1->next=p;		//采用尾插法将p(data值为ai)插入L1中
	r1=p;
	p=p->next;		//p移向下一个结点(data值为bi)
	q=p->next;     	//用q保存p的后继结点
	p->next=L2->next;	//采用头插法将p插入L2中
	L2->next=p;
	p=q;			//p重新指向ai+1的结点
   }
   r1->next=NULL;		//尾结点next置空
}

删除一个单链表L中元素值最大的结点（唯一）

void delmaxnode(LinkNode *&L)
{   LinkNode *p=L->next，*pre=L，*maxp=p，*maxpre=pre;

    while (p!=NULL)
    {  if (maxp->data<p->data)	//若找到一个更大的结点
	{   maxp=p;			//更改maxp
	    maxpre=pre;		//更改maxpre
	}
	pre=p;				//p、pre同步后移一个结点
	p=p->next;
    }

    maxpre->next=maxp->next;		//删除maxp结点
    free(maxp);			//释放maxp结点
}

使L其元素递增有序排列

void sort(LinkNode *&L)
{ 
   LinkNode *p，*pre，*q;
   p=L->next->next;		//p指向L的第2个数据结点
   L->next->next=NULL;	//构造只含一个数据结点的有序表
       
   while (p!=NULL)
   {	q=p->next;		 //q保存p结点后继结点的指针

	pre=L;  	        //从有序表开头，pre指向插入p的前驱结点
	while (pre->next!=NULL && pre->next->data<p->data)
	      pre=pre->next;	 //在有序表中找插入p的前驱结点pre

	p->next=pre->next;
	pre->next=p;
	p=q;			//扫描原单链表余下的结点
   }
}

双链表

类型定义

typedef struct DNode       	//双链表结点类型
{  ElemType data;
   struct DNode *prior;    	//指向前驱结点
   struct DNode *next;     	//指向后继结点
} DLinkNode;

头插法建表

void CreateListF(DLinkNode *&L，ElemType a[]，int n)
{  DLinkNode *s; int i;
   L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
   L->prior=L->next=NULL;	//前后指针域置为NULL
   for (i=0;i<n;i++)		//循环建立数据结点
   {	s=(DLinkNode *)malloc(sizeof(DLinkNode));
	s->data=a[i];		//创建数据结点s
	s->next=L->next;	//将s插入到头结点之后
	if (L->next!=NULL)   	//若L存在数据结点，修改前驱指针
  	    L->next->prior=s;
       L->next=s;
       s->prior=L;
   }
} 

尾插法建表

void CreateListR(DLinkNode *&L，ElemType a[]，int n)
{  DLinkNode *s，*r;
   int i;
   L=(DLinkNode *)malloc(sizeof(DLinkNode));    //创建头结点
   r=L;					//r始终指向尾结点，开始时指向头结点
   for (i=0;i<n;i++)			//循环建立数据结点
   {  s=(DLinkNode *)malloc(sizeof(DLinkNode));
      s->data=a[i];			//创建数据结点s
      r->next=s;s->prir=r;		//将s插入r之后
      r=s;				//r指向尾结点
   }
   r->next=NULL;			//尾结点next域置为NULL
}

插入

bool ListInsert(DLinkNode *&L，int i，ElemType e)
{  int j=0;
   DLinkNode *p=L，*s;	      	//p指向头结点，j设置为0
   while (j<i-1 && p!=NULL)	//查找第i-1个结点
   {  j++;
      p=p->next;
   }      
  if (p==NULL)			//未找到第i-1个结点，返回false
     return false;
  else				//找到第i-1个结点p，在其后插入新结点s
  {
	s=(DLinkNode *)malloc(sizeof(DLinkNode));
	s->data=e;		//创建新结点s
	s->next=p->next;	//在p之后插入s结点
	if (p->next!=NULL)	//若存在后继结点，修改其前驱指针
   	     p->next->prior=s;
	s->prior=p;
	p->next=s;
	return true;
   }
}

删除

bool ListDelete(DLinkNode *&L，int i，ElemType &e)
{  int j=0; DLinkNode *p=L，*q; 	//p指向头结点，j设置为0
   while (j<i-1 && p!=NULL)	  	//查找第i-1个结点
   {  j++;
      p=p->next;
   }
   if (p==NULL)			//未找到第i-1个结点
	return false;
   else			   		//找到第i-1个结点p
   {	q=p->next;			//q指向第i个结点
	if (q==NULL)	   		//当不存在第i个结点时返回false
	   return false;
	e=q->data;
	p->next=q->next;		//从双单链表中删除q结点
	if (q->next!=NULL)    	//若q结点存在后继结点
            q->next->prior=p;		//修改q结点后继结点的前驱指针
	free(q);		   	//释放q结点
	return true;
   }
}

链表元素逆置

void reverse(DLinkNode *&L)		//双链表结点逆置
{  DLinkNode *p=L->next，*q;		//p指向开始结点
   L->next=NULL;			//构造只有头结点的双链表L
   while (p!=NULL)			//扫描L的数据结点
   {	q=p->next;	      		//用q保存其后继结点

	p->next=L->next;		//采用头插法将p结点插入
	if (L->next!=NULL)		//修改其前驱指针
  	   L->next->prior=p;
	L->next=p;
	p->prior=L;

	p=q;				//让p重新指向其后继结点
   }
}

使L其元素递增有序排列。

void sort(DLinkNode *&L)	//双链表结点递增排序
{  DLinkNode *p,*pre,*q;
   p=L->next->next;		//p指向L的第2个数据结点
   L->next->next=NULL;	//构造只含一个数据结点的有序表
   while (p!=NULL)
   {  q=p->next;		//q保存p结点后继结点
      pre=L;	 		//从L开头比较,pre指向插入结点p的前驱结点
      while (pre->next!=NULL && pre->next->data<p->data)
         pre=pre->next;	//在有序表中找插入结点的前驱结点pre
      p->next=pre->next;	//在pre结点之后插入结点p
      if (pre->next!=NULL)
         pre->next->prior=p;
      pre->next=p;
      p->prior=pre;
      p=q;			//扫描原双链表余下的结点
   }
}

循环链表

统计L其data域值为X的个数

int count(LinkNode *L,ElemType x)
{  int cnt=0;
   LinkNode *p=L->next;		//p指向首结点,cnt置为0
   while (p!=L)			//扫描循环单链表L
   {  if (p->data==x)
         cnt++;			//找到值为x的结点后cnt增1
      p=p->next;			//p指向下一个结点
   }
   return cnt;				//返回值为x的结点个数
}

循环双链表

删除第一个data域值为x的结点

bool delelem(DLinkNode *&L,ElemType x)
{  DLinkNode *p=L->next;	   	//p指向首结点
   while (p!=L && p->data!=x)	//查找第一个data值为x的结点p
      p=p->next;
   if (p!=L)				//找到了第一个值为x的结点p
   {  p->next->prior=p->prior;  //删除p结点
      p->prior->next=p->next;
      free(p);
      return true;			//返回真
   }
   else				//没有找到为x的结点，返回假
      return false;
}

判断带头结点的L是否对称相等

bool Symm(DLinkNode *L)
{  bool same=true;
   DLinkNode *p=L->next;	 	//p指向首结点
   DLinkNode *q=L->prior;     	//q指向尾结点
   while (same)
   {
      if  (p->data!=q->data)
          same=false;
      else  
      {   if (p==q || p==q->prior) break;
	   q=q->prior;	 		//q前移
          p=p->next;			//p后移
      }
   }
   return same;
}

有序表

插入

void ListInsert(SqList *&L，ElemType e)
{  int i=0，j;
   while (i<L->length && L->data[i]<e)
      i++;				//查找值为e的元素
   for (j=ListLength(L);j>i;j--)	//将data[i..n]后移一个位置
      L->data[j]=L->data[j-1]; 
   L->data[i]=e;
   L->length++;			//有序顺序表长度增1
}

void ListInsert(LinkNode *&L，ElemType e)
{  LinkNode *pre=L，*p;

   while (pre->next!=NULL && pre->next->data<e)
	pre=pre->next; 	//查找插入结点的前驱结点pre

   p=(LinkNode *)malloc(sizeof(LinkNode));
   p->data=e;			//创建存放e的数据结点p
   p->next=pre->next;		//在pre结点之后插入p结点
   pre->next=p;
}

代码实现

顺序表代码实现

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h> //内存分配空间
#define MaxSize 50 //定义整型常量 
#include <stdbool.h>  
typedef int ElemType;//自定义数据类型，假设ElemType为int类型 
typedef struct
{
	ElemType data[MaxSize]; //存放线性表中的元素 
	int length;//存放线性表的长度 
} SqList;//顺序表类型 

//创建线性表
//方法:将给定的含有个n元素的数组的每个元素依次放入到顺序表中，
//并将给n赋值给顺序表的长度成员 L->length 
void CreateList(SqList *&L,ElemType a[],int n)//由a中的n个元素建立顺序表 
{			//引用参数：将执行结果回传给实参；传递顺序表指针 
	int i=0;
	L=(SqList *)malloc(sizeof(SqList));//求出SqList的内存长度， 
	for(i=0;i<n;i++)				//并转换为SqList类型的指针，赋值给L 
	L->data[i]=a[i];
	L->length=n; 
 } //时间复杂度是O(n)
 
 //初始化线性表 
void InitList(SqList *&L)//引用型指针 
{
	L=(SqList *)malloc(sizeof(SqList)); 
	L->length=0;	//置空线性表的长度 
}

//销毁线性表 
void DestroyList(SqList *&L)
{
	free(L);//释放L所指的顺序表空间 
 } 
 
 //判断是否为空表 
bool ListEmpty(SqList *L)
{
	return(L->length==0);
	//空表返回true，否者返回false 
 } 
 
 //求数据表的长度
 int ListLength(SqList *L)
 {
 	return(L->length);//直接返回数据域length 
  } 
  
//输出线性表
void DispList(SqList *L)
{
	int i;
	if(ListEmpty(L))//先判断是否为空，true继续 
	return;
	for(i=0;i<L->length;i++)
		printf(" %d",L->data[i]);
	printf("\n"); 
 } 
 
 //按序号求线性表中的元素
 bool GetElem(SqList *L,int i,ElemType &e)
 {
 	if(i<1||i>L->length)
 	return false;   //判断是否在表中 
 	e=L->data[i-1];//i是逻辑顺序,i-1是物理顺序，求出下标，并取元素的值 
 	return true;
 }
 
 //按元素查找 
 //如果遍历完整个列表都没有找到元素a，函数返回0。
 //如果找到了元素a，函数返回它在列表中的位置（从1开始计数）。
 int LocateElem(SqList *L,ElemType a)
 {
 	int i=0;
 	while(i<L->length&&L->data[i])
 	i++;
 	if(i>=L->length)
 	return 0;
 	else
 		return i+1;
  } 
 
 //插入数据
 bool ListInsert(SqList *&L,int i,ElemType e) 
 {
 int j;
 if(i<1||i>L->length+1||L->length==MaxSize)
 return false;//表示线性表元素在表外 
 i--;//将逻辑序号转换为物理序号（下标）
 for(j=L->length;j>i;j--)
 L->data[j]=L->data[j-1];//将data[i]及后面的元素后移一个位置
 L->data[i]=e;
 L->length++;
 return true; 
 }
 
 //删除元素数据
bool ListDelete(SqList *&L,int i,ElemType &e)
{
	int j;
	if(i<1||i>L->length)
		return false;//不在表中 
	i--;//将逻辑序号转换为物理序号（下标）
	e=L->data[i];//将位置i的元素赋值给e。 
	for(j=i;j<L->length-1;j++)//下标 
		L->data[j]=L->data[j+1];//将data[i]之后的元素前移一个元素 
	L->length--;//顺序表的长度减一 
	return true;
}
  
 
int main()//测试函数 
{
	SqList *sq;//分配空间，保存的指针值 
	ElemType x[20]={1,2,3,4,5,6,6};
	CreateList(sq,x,7);
	printf("原始线性表：");
	DispList(sq);
	ElemType d=2;
    ListInsert(sq,2,d);
    printf("插入后的线性表：");//在元素2之后上插入2 
	DispList(sq);
	
	ElemType f;
	ListDelete(sq,4,f);
	printf("删除的元素是：");// 删除第4个元素 
	DispList(sq);
	
    printf("输出线性表的长度："); 
	ListLength(sq);
	int length = ListLength(sq);
	printf("%d\n",length);
	
	ElemType w=2;
    int b;
    b=LocateElem(sq,w);
    printf("存在这个元素吗：存在的话在第几位：%d\n",b);
	
	ElemType e;
//    bool a = true;  
//    bool b = false;  
    printf("线性表中存第3个元素吗："); 
    printf("%d\n",GetElem(sq,3,e)); 
    
   
    
	return 0; 
} 

单链表代码实现

#include <stdio.h>
#include <malloc.h> 
typedef int ElemType;//数据域可以为其他类型

typedef struct LNode//定义单链表节点类型
{
	ElemType data;//数据域
	struct LNode *next;//指针域，指向后继节点
}LinkNode;
//头插法建立单链表 
void CreateListF(LinkNode *&L,ElemType a[],int n)
{
	LinkNode *s;
	L=(LinkNode *)malloc(sizeof(LinkNode));
	L->next=NULL;
	for(int i=0;i<n;i++)
	{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=a[i];
		s->next=L->next;
		L->next=s;
	}
}
//尾插法建立单链表
void CreateLsitR(LinkNode *&L,ElemType a[],int n)
{
	LinkNode *s,*r;
	L=(LinkNode *)malloc(sizeof(LinkNode));
	r=L;
	for(int i=0;i<n;i++)
	{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=a[i];
		r->next=s;
		r=s;
	} 
	r->next=NULL;
 } 
//初始化单链表
void InitList(LinkNode *&L)
{
	L=(LinkNode *)malloc(sizeof(LinkNode));
	L->next=NULL;
} 

//输出单链表
void DisList(LinkNode *L)
{
	LinkNode *p=L->next;
	while(p!=NULL)
	{
		printf(" %d",p->data);
		p=p->next;
	}
	printf("\n");
 } 
bool ListEmpty(LinkNode *L)
{
	return(L->next==NULL);	
} 
//线性表的长度
int ListLength(LinkNode *L)
{
	int n=0;
	LinkNode *p=L;
	while(p->next!=NULL)
	{
		n++;
		p=p->next;
	}
	return(n);
 } 
 
 //按序号求表中的元素
 bool GetElem(LinkNode *L,int i,ElemType &e)
 {
 	int j=0;
 	LinkNode *p=L;
 	if(i<=0)return false;
 	while(j<i&&p!=NULL)
 	{
 		j++;
 		p=p->next;
	 }
	 if(p==NULL)return false;
	 else
	 {
	 	e=p->data;
	 	return true;
	 }
  } 
 
 //按元素值查找
 int LocateElem(LinkNode *L,ElemType e)
 {
 	int i =1;
 	LinkNode *p=L->next;
 	while(p!=NULL&&p->data!=e)
 	{
 		p=p->next;
 		i++;
	 }
	 if(p==NULL)
	 return(0);
	 else
	 return(i);
  } 
//插入数据元素 
bool ListInsert(LinkNode *&L,int i,ElemType e)
{
	int j=0;
	LinkNode *p=L,*s;
	if(i<=0) return false;
	while(j<i-1&&p!=NULL)
	{
		j++;
		p=p->next;
	}
	if(p==NULL)
	return false;
	else
	{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=e;
		s->next=p->next;
		p->next=s;
		return true;
	}
	
 } 
 
//删除数据元素
bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
	int j=0;
	LinkNode *p=L,*q;
	if(i<=0)return false;
	while(j<i-1&&p!=NULL)
	{
		j++;
		p=p->next;
	}
	if(p==NULL)
	return false;
	else
	{
		q=p->next;
		if(q==NULL)
		return false;
	e=q->data;
	p->next=q->next;
	free(q);
	return true;
	}
 } 
//测试函数
int main()
{
	LinkNode *L;
	ElemType x[20]={1,2,3,4,5,6,7};
	printf("头插法建立单链表：\n");
	CreateListF(L,x,7);
	//InitList(L);
	DisList(L);
	printf("尾插法建立单链表：\n");
	CreateLsitR(L,x,7);
	DisList(L);
	
	int a;
	a=ListLength(L);
	printf("输出单链表的长度：%d\n",a);
	
	int b;
	b=ListEmpty(L);
	printf("这个单链表是否为空：%d\n",b);
	
	ElemType c;
	printf("找到第3个数据结点：%d\n",GetElem(L,3,c));
	
	ElemType d=5;
	printf("第一个值域为5的结点的逻辑序号为：%d\n",LocateElem(L,d));
	
	ElemType e=2;
	ListInsert(L,2,e);
	printf("插入后的链表：\n");
	DisList(L);
	
	ElemType f=2;
	ListDelete(L,2,f);
	printf("删除后的链表：\n");
	DisList(L);
	
	
 } 

栈代码实现

判断表达式中的括号是否正确配对
#include <stdio.h>
#include <malloc.h> 
#include <stdlib.h>
#define MaxSize 50
typedef char ElemType;
typedef struct
{
	ElemType data[MaxSize];
	int top;
}SqStack;
void InitStack(SqStack *&s)
{
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top=-1;
}
DestroyStack(SqStack *&s)
{
	free(s);
}
bool StackEmpty(SqStack *s)
{
	return (s->top==-1); 
}
bool GetTop (SqStack *s,ElemType &e)
{
	if(s->top==-1)
	return false;
	e=s->data[s->top];
	return true;
}
bool Push(SqStack *&s,ElemType e)
{
	if(s->top==MaxSize-1)
	return false;
	s->top++;
	s->data[s->top]=e;
	return true;
}
bool Pop(SqStack *&s,ElemType &e)
{
	if(s->top==-1)
	return false;
	e=s->data[s->top];
	s->top--;
	return true;
}
bool Match(char exp[],int n)
{	SqStack *ls;
	InitStack(ls);
	int i=0;
	ElemType e;
	bool flag=true;
	while (i<n && flag)
	{	if (exp[i]=='(' || exp[i]=='[' || exp[i]=='{')
			Push(ls,exp[i]); //遇到'('、'['或'{',则将其进栈
		if (exp[i]==')') //遇到')',若栈顶是'(',则继续处理,否则以不配对返回
		{	if (GetTop(ls,e))
			{	if (e=='(') Pop(ls,e);
				else flag=false;
			}
			else flag=false;
		}
		if (exp[i]==']') //遇到']',若栈顶是'[',则继续处理,否则以不配对返回
		{	if (GetTop(ls,e))
			{	if (e=='[') Pop(ls,e);
				else flag=false;
			}
			else flag=false;
		}
		if (exp[i]=='}') //遇到'}',若栈顶是'{',则继续处理,否则以不配对返回
		{	if (GetTop(ls,e))
			{	if (e=='{') Pop(ls,e);
				else flag=false;
			}
			else flag=false;
		}
		i++;
	}
	if (!StackEmpty(ls)) flag=false; //若栈不空,则不配对
	DestroyStack(ls);
	return flag;
}
int main()
{ 
    char exp[] = "{a,a,(b,b),c,c}";  
    int n = sizeof(exp) / sizeof(char); //计算字符串数组的长度，也就是字符串中的字符数。 
    bool result = Match(exp, n);  
    printf("Result: %s\n", result ? "true" : "false");  
    return 0;  
}

队列的代码实现

数字进队，小写字母出队，其他字符输入结束
#include <stdio.h>
#include <malloc.h> 
#include <stdlib.h>
#define MaxSize 10
typedef int ElemType;
typedef struct
{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;
void InitQueue(SqQueue *&q)
{
	q=(SqQueue *)malloc(sizeof(SqQueue));
	q->front=q->rear=-1;
}
void DestroyQueue (SqQueue *&q)
{
	free(q);
}
bool enQueue (SqQueue *&q,ElemType e)
{
	if(q->rear==MaxSize-1)
	return false;
	q->rear++;
	q->data[q->rear]=e;
	return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{
	if(q->front==q->rear)
	return false;
	q->front++;
	e=q->data[q->front];
	return true; 
}
bool QueueEmpty(Squeue *q)
{
    return (q->front==q->rear);
}

void fun()
{ 	ElemType a,e;
	SqQueue *qu; //定义队列指针
	InitQueue(qu);
	while (true)
	{	printf("输入 a:");
		scanf("%s",&a);
		if (a>='0' && a<='9') //为数字字符
		{	if (!enQueue(qu,a))
				printf(" 队列满,不能进队\n");
		}
		else if (a>='a' && a<='z') //为小写字母
		{	if (!deQueue(qu,e))
				printf(" 队列空,不能出队\n");
			else
				printf(" 出队元素:%c\n",e);
		}
		else break; //为其他字符
		}
	DestroyQueue(qu);
}
int main()
{
	fun();
}

串的代码实现

//递归求串s 的逆串
#include "stdio.h"
#define MaxSize 50
typedef struct
{
	char data[MaxSize];
	int length;
}SqString;
int StrLength(SqString s)
 {
 	return(s.length);
} 
SqString InsStr(SqString s1,int i,SqString s2) 
{
    int j;
    SqString str;
    str.length=0;  
    if(i<=0||i>s1.length+1)  
        return str;
    for(j=0; j<i-1; j++)
        str.data[j]=s1.data[j];
    for(j=0; j<s2.length; j++)
        str.data[i+j-1]=s2.data[j];
    for(j=i-1; j<s1.length; j++)
        str.data[s2.length+j]=s1.data[j];
    str.length=s1.length+s2.length;
    return str;
}
void StrCopy(SqString &s, SqString t)
 {
    for(int i=0; i<t.length; i++) 
	{
        s.data[i]=t.data[i]; 
    }
    s.length=t.length; 
}
SqString Concat(SqString s,SqString t) 
{
    SqString str;
    int i;
    str.length=s.length+t.length;
    for(i=0; i<s.length; i++)
        str.data[i]=s.data[i];
    for(i=0; i<t.length; i++)
        str.data[s.length+i]=t.data[i];
    return str;
}
SqString SubStr(SqString s,int i,int j) 
{
    int k;
    SqString str;
    str.length=0;
    if(i<=0||i>s.length||j<0||i+j-1>s.length)
        return str;
    for(k=i-1; k<i+j-1; k++)
        str.data[k-i+1]=s.data[k];
    str.length=j;
    return str;
}
SqString invert(SqString s)
{	SqString s1,s2;
	if (StrLength(s)>0)
	{	s1=invert(SubStr(s,2,StrLength(s)-1));
		s2=Concat(s1,SubStr(s,1,1));
	}
	else
		StrCopy(s2,s);
	return s2;
}
int main() 
{  
    SqString s = {"Hello,world", 11};  
    SqString Invert = invert(s);  
    for(int i = 0; i < Invert.length; i++) {  
        printf("%c", Invert.data[i]);  
    }  
    return 0;  
}

递归的代码实现

//判断几位数
#include <stdio.h>
int fun(int n)
{	if (n<10)
		return 1;
	else
		return fun(n/10)+1;
}
int main()
{
	int n;
	printf("输入正整数n:\n"); 
	scanf("%d",&n);
	printf("n是%d位数",fun(n));
	
}

二叉树代码实现

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50 
typedef  char ElemType;
typedef struct node 
{
	ElemType data;
	struct node *lchild;
	struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&b,char *str)     //由str串创建二叉链
{
    BTNode *St[MaxSize],*p=NULL;
    int top=-1,k,j=0;
    char ch;
    b=NULL;             //建立的二叉树初始时为空
    ch=str[j];
    while (ch!='\0')    //str未扫描完时循环
    {
        switch(ch)
        {
        case '(':
            top++;
            St[top]=p;
            k=1;
            break;      //为左节点
        case ')':
            top--;
            break;
        case ',':
            k=2;
            break;                          //为右节点
        default:
            p=(BTNode *)malloc(sizeof(BTNode));
            p->data=ch;
            p->lchild=p->rchild=NULL;
            if (b==NULL)                    //p指向二叉树的根节点
                b=p;
            else                            //已建立二叉树根节点
            {
                switch(k)
                {
                case 1:
                    St[top]->lchild=p;
                    break;
                case 2:
                    St[top]->rchild=p;
                    break;
                }
            }
        }
        j++;
        ch=str[j];
    }
}

void DispBTNode(BTNode *b)
{
	if(b!=NULL)
	{
		printf("%c",b->data);
		if(b->lchild!=NULL||b->rchild!=NULL)
		{
			printf("(");
			DispBTNode(b->lchild);
			if(b->rchild!=NULL) printf(",");
			DispBTNode(b->rchild);
			printf(")");
		}
	}
}
int BTHeight (BTNode *b)
{
	int lchildh,rchildh;
	if(b==NULL)return(0);
	else
	{
		lchildh=BTHeight(b->lchild);
		rchildh=BTHeight(b->rchild);
		return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
	}
 } 
 BTNode * FindNode(BTNode *b,ElemType x) 
 {
 	BTNode *p;
 	if(b==NULL)return NULL;
 	else if (b->data==x)
 	return b;
 		else 
 			{
 				p=FindNode(b->lchild,x);
 				if(p!=NULL)
 				return p;
 				else
 					return FindNode(b->rchild,x);
			 }
 }
 BTNode *LchildNode(BTNode *p)
 {
 	return p->lchild;
 }
  BTNode *RchildNode(BTNode *p)
 {
 	return p->rchild;
 }
 void PreOrder(BTNode *b)
 {
 	if(b!=NULL)
 	{
 		printf("%c",b->data);
 		PreOrder(b->lchild);
 		PreOrder(b->rchild);
	 }
 }
  void InOrder(BTNode *b)
 {
 	if(b!=NULL)
 	{
 		
 		PreOrder(b->lchild);
 		printf("%c",b->data);
 		PreOrder(b->rchild);
	 }
 }
 void PostOrder(BTNode *b)
 {
 	if(b!=NULL)
 	{
 		PostOrder(b->lchild);
 		PostOrder(b->rchild);
 		printf("%c",b->data);
	 }
 }
 int Nodes(BTNode *b)
 {
 	if(b==NULL) return 0;
 	else return Nodes(b->lchild)+Nodes(b->rchild)+1;
 }
 void Displeaf(BTNode *b)
 {
 	if(b!=NULL)
 	{
 		if(b->lchild==NULL&&b->rchild==NULL)
 			printf("%c",b->data);
 		Displeaf(b->lchild);
 		Displeaf(b->rchild);
	 }
 }
 int Level(BTNode *b,ElemType x,int h)
 {
 	int l;
 	if(b==NULL) return (0);
 	else if(b->data==x)
 		return (h);
 		else
    		{
       		 // 修改这里：在左右子树中查找时都增加层级
        		l = Level(b->lchild, x, h + 1);
        		if (l != 0)
            		return (l);
        		else
            		return (Level(b->rchild, x, h + 1));
    }
  } 
void Lnodenum (BTNode *b,int h,int k,int &n)
{
	if(b==NULL)
		return;
	else
	{
		if(h==k) n++;
		else if(h<k)
		{
			Lnodenum(b->lchild,h+1,k,n); 
			Lnodenum(b->rchild,h+1,k,n);
		}
	}
}
bool Like(BTNode *b1,BTNode *b2)
//b1和b2两二叉树相似时返回true，否则返回false 
{
	bool like1,like2;
	if(b1==NULL&&b2==NULL)
		return true;
	else if(b1==NULL||b2==NULL)
		return false;
		else 
		{
			like1=Like(b1->lchild,b2->lchild);
			like2=Like(b1->lchild,b2->lchild);
			return (like1&&like2);
		}
}
bool ancestor (BTNode *b,ElemType x)
{
	if(b==NULL)
		return false;
			//节点b的左右孩子节点的data域为x 
	else if (b->lchild!=NULL&&b->lchild->data==x||b->rchild!=NULL&&b->rchild->data==x)
			{
				printf("%c",b->data);
				return true;
			}
				//若左右孩子为true 
			else if(ancestor(b->lchild,x)||ancestor(b->rchild,x))
			{
				printf("%c",b->data);
				return true;
			}
			else return false;
}
 
int main()
{
	BTNode *b,*p,*lp,*rp,*b1,*b2;
    CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    CreateBTNode(b1,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    CreateBTNode(b2,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("\n");
    printf("  输出二叉树:");
    DispBTNode(b);
    printf("\n");
    printf("  输出二叉树的高度:%d",BTHeight(b));
    printf("\n");
    printf("  查找H节点:");
    p=FindNode(b,'H');
    if (p!=NULL)
    {
        lp=LchildNode(p);
        if (lp!=NULL)
            printf("左孩子为%c ",lp->data);
        else
            printf("无左孩子 ");
        rp=RchildNode(p);
        if (rp!=NULL)
            printf("右孩子为%c",rp->data);
        else
            printf("无右孩子 ");
    }
    else
        printf(" 未找到！");
    printf("\n");
    printf("  先序遍历：");
    PreOrder(b);
    printf("\n");
    printf("  中序遍历：");
    InOrder(b);
    printf("\n");
    printf("  后序遍历：");
    PostOrder(b);
    printf("\n");
    printf("  二叉树的总结点数：%d",Nodes(b));
    printf("\n");
    printf("  二叉树所有的叶子结点：");
    Displeaf(b);
    printf("\n");
    ElemType X;
    int h; 
    printf("  输入要查找的结点值："); 
    scanf("%c",&X); 
    h=Level(b,X,1);
	if(h==0)
		printf("  b不存在%c结点\n",X);
		
	else 
		printf("  在b中%c结点的层次为%d\n",X,h);
	printf("\n");	
	int k ;//第几层
	printf("  求节点数的层数为："); 
	scanf("%d",&k);
    int n = 0;//有几个结点 
    Lnodenum(b, 1, k, n);
    printf("  第%d的结点个数是%d", k, n);
	printf("\n");
	printf("  判断b1和b2是否相似：\n");
	 bool result;
	 result=Like(b1,b2);
	 if (result)
        printf("  The two binary trees are similar.\n");
    else
        printf("  The two binary trees are not similar.\n");
    
    char Z='N';
    printf("  求N的祖先结点为:");
    //scanf("%c",&Z);
	ancestor(b,Z); 
    return 0;
}