devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言之常用数据结构_c语言中数据结构有？

作者：你好赵伟 | 2024-04-09 09:23:53

赞

踩

c语言中数据结构有？

目录

 

一、顺序表

二、单链表

三、双向链表

三、顺序栈

四、循环队列

五、二叉树

一、顺序表

顺序表是线性表的顺序存储，通过一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。假定线性表的元素类型为ElemType，则线性表的顺序存储类型描述为：

  1.     //静态分配
  2.     #define MaxSize 50
  3.     typedef int ElemType;
  4.     typedef struct{
  5. 	    ElemType data[MaxSize];
  6. 	    int length;
  7.     }SqList;

C语言中一维数组可以进行动态分配避免溢出；

（1）插入操作

  1.     bool ListInsert(SqList &L,int i,ElemType e){
  2.         //在顺序表L的第i（1<=i<=L.length+1）个位置插入新元素e
  3. 	    if(i<1 || i>L.length+1)
  4. 	    	return false;
  5. 	    if(L.length>=MaxSize)
  6. 		    return false;
  7. 	    for(int j=L.length;j>=i;j--)            //将第i个元素及之后的元素后移
  8. 		    L.data[j]=L.data[j-1];
  9. 	    L.data[i-1]=e;
  10. 	    L.length++;
  11. 	    return true;
  12.     }

（2）删除操作

  1.     bool ListDelete(SqList &L,int i, ElemType &e){
  2.     //删除顺序表L中第i个未知的元素
  3. 	if(i<1 || i>L.length)
  4. 		return false;
  5. 	e=L.data[i-1];
  6. 	for(int j=i;j<L.length;j++)
  7. 		L.data[j-1]=L.data[j];
  8. 	L.length--;
  9. 	return true;
  10.     }

（3）按值查找

  1.     bool LocateElem(SqList &L,ElemType e){
  2.     //查找顺序表中值为e的元素，查找成功则返回元素位置，否则返回0
  3. 	int i;
  4. 	for(int i=0;i<L.length;i++)
  5. 		if(L.data[i]==e)
  6. 			return i+1;
  7. 	return 0;
  8.     }

 

二、单链表

单链表是线性表的链式存储，通过一组任意的储存单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。单链表中的节点类型如下：

  1.     typedef struct LinkNode{
  2.         ElemType data;
  3.         struct LinkNode *next;
  4.     }LinkNode, *LinkList;

通常用头指针来标识一个单链表，此外为了操作上的方便，在单链表第一个节点之前附加一个结点，称为头结点。

（1）建立单链表

  1.     LinkList CreatList1(LinkList &L){ 
  2.     //头插法建立单链表
  3. 	LNode *s;int x;
  4. 	L=(LinkList)malloc(sizeof(LNode));
  5. 	L->next=NULL;
  6. 	scanf("%d",&x);
  7. 	while(x!=9999){
  8. 		s=(LNode*)malloc(sizeof(LNode));
  9. 		s->data=x;
  10. 		s->next=L->next;
  11. 		L->next=s;
  12. 		scanf("%d",&x);
  13. 	}
  14. 	return L;
  15.     } 
  16.  
  17.     LinkList CreatList2(LinkList &L){
  18.     //尾插法建立单链表
  19. 	int x;
  20. 	L=(LinkList)malloc(sizeof(LNode));
  21. 	LNode *s,*r=L;
  22. 	scanf("%d",&x);
  23. 	while(x!=9999){
  24. 		s=(LNode*)malloc(sizeof(LNode));
  25. 		s->data=x;
  26. 		r->next=s;
  27. 		r=s;
  28. 		scanf("%d",&x);
  29. 	}
  30. 	r->next=NULL;
  31. 	return L;
  32.     } 
  33.

（2）按序号查找节点值

  1.     LNode *GetElem(LinkList L,int i){
  2.     //取出单链表L（带头节点）中第i个位置的结点指针
  3. 	    int j=1;
  4. 	    LNode *p=L->next;
  5. 	    if(i==0)
  6. 		    return L;
  7. 	    if(i<1)
  8. 		return NULL;
  9. 	    while(p&&j<i){
  10. 		    p=p->next;
  11. 		    j++;
  12. 	    }
  13. 	    return p;
  14.     }

（3）按值查找表结点

  1.     LNode *LocateElem(LinkList L,ElemType e){
  2.     //查找单链表L（带头结点）中数据值等于e的结点指针，否则返回NULL
  3. 	    LNode *p=L->next;
  4. 	    while(p!=NULL&&p->data!=e)
  5. 		    p=p->next;
  6. 	    return p;
  7.     }

（4）插入结点

  1.     bool ListFrontInsert(LinkList L,int i,ElemType e){
  2.     //将值为x的新节点插入到单链表的第i个位置桑
  3. 	LinkList p=GetElem(L,i-1);
  4. 	    if(NULL==p){
  5. 		    return false;
  6. 	    }
  7. 	    LinkList s=(LNode*)malloc(sizeof(LNode));
  8. 	    s->data=e;
  9. 	    s->next=p->next;
  10. 	    p->next=s;
  11. 	    return true;
  12.     }

三、双向链表

双向链表在单链表的基础上增加了一个指向其前驱的prior指针，结点类型及相关函数描述如下：

  1.     typedef int ElemType;
  2.     typedef struct DNode{
  3. 	    ElemType data;
  4. 	    struct DNode *prior,*next;
  5.     }DNode,*DLinkList;
  6.  
  7.     DLinkList Dlist_head_insert(DLinkList &DL){ 
  8.     //头插法
  9. 	DNode *s;int x;
  10. 	DL=(DLinkList)malloc(sizeof(DNode));
  11. 	DL->next=NULL;
  12. 	DL->prior=NULL;
  13. 	scanf("%d",&x);
  14. 	while(x!=9999){
  15. 		s=(DNode*)malloc(sizeof(DNode));
  16. 		s->data=x;
  17. 		s->next=DL->next;
  18. 		if(DL->next!=NULL){
  19. 			DL->next->prior=s;
  20. 		}
  21. 		s->prior=DL;
  22. 		DL->next=s;
  23. 		scanf("%d",&x);
  24. 	}
  25. 	return DL;
  26.     } 
  27.  
  28.     DLinkList Dlist_tail_insert(DLinkList &DL){
  29.     //尾插法
  30. 	int x;
  31. 	DL=(DLinkList)malloc(sizeof(DNode));
  32. 	DNode *s,*r=DL;
  33. 	DL->prior=NULL;
  34. 	scanf("%d",&x);
  35. 	while(x!=9999){
  36. 		s=(DNode*)malloc(sizeof(DNode));
  37. 		s->data=x;
  38. 		r->next=s;
  39. 		s->prior=r;
  40. 		r=s;
  41. 		scanf("%d",&x);
  42. 	}
  43. 	r->next=NULL;
  44. 	return DL;
  45.     } 
  46.  
  47.     DNode *GetElem(DLinkList DL,int i){
  48.     //返回第i个位置的结点指针
  49. 	int j=1;
  50. 	DNode *p=DL->next;
  51. 	if(i==0)
  52. 		return DL;
  53. 	if(i<1)
  54. 		return NULL;
  55. 	while(p&&j<i){
  56. 		p=p->next;
  57. 		j++;
  58. 	}
  59. 	return p;
  60.     }
  61.     
  62.     bool DListFrontInsert(DLinkList DL,int i,ElemType e){
  63.     //插入结点
  64. 	DLinkList p=GetElem(DL,i-1);
  65. 	if(NULL==p){
  66. 		return false;
  67. 	}
  68. 	DLinkList s=(DNode*)malloc(sizeof(DNode));
  69. 	s->data=e;
  70. 	s->next=p->next;
  71. 	p->next->prior=s;
  72. 	s->prior=p;
  73. 	p->next=s;
  74. 	return true;
  75.     }
  76.     
  77.     bool DListDelete(DLinkList DL,int i){
  78.     //删除第i个结点
  79. 	DLinkList p=GetElem(DL,i-1);
  80. 	if(NULL==p){
  81. 		return false;
  82. 	}
  83. 	DLinkList q;
  84. 	q=p->next;
  85. 	if(q==NULL)
  86. 		return false;
  87. 	p->next=q->next;
  88. 	if(q->next!=NULL){ //删除最后一个元素，需要的判断 
  89. 		q->next->prior=p;
  90. 	}
  91. 	free(q);
  92. 	return true;
  93.     }
  94.

三、顺序栈

顺序栈是采用顺序存储的栈，它利用一组地址连续的储存单元存放自栈底到栈顶的数据元素，同时设一个指针top指示当前栈顶位置。

  1.     //实现栈 可以用数组，也可以用链表 
  2.     #define MaxSize 50
  3.     typedef int ElemType;
  4.     typedef struct {
  5.         ElemType data[MaxSize];
  6.         int top;
  7.     }SqStack;
  8.     
  9.     typedef struct LinkNode{
  10.         ElemType data;
  11.         struct LinkNode *next;
  12.     }*LiStack;
  13.  
  14.     void InitStack(SqStack &S){
  15.     //初始化
  16. 	S.top=-1;
  17.     }
  18.  
  19.     bool StackEmpty(SqStack &S){
  20.     //栈判空
  21. 	if(S.top==-1)
  22. 		return true;
  23. 	else
  24. 		return false;
  25.     }
  26.  
  27.     bool Push(SqStack &S,ElemType x){
  28.     //进栈
  29. 	if(S.top==MaxSize-1){
  30. 		return false;
  31. 	}
  32. 	S.data[++S.top]=x;
  33. 	return true;
  34.     }
  35.  
  36.     bool Pop(SqStack &S,ElemType &x){
  37.     //出栈
  38. 	if(-1==S.top)
  39. 		return false;
  40. 	x=S.data[S.top--];
  41. 	return true;
  42.     }
  43.  
  44.     bool GetTop(SqStack &S,ElemType &x){
  45.     //读取栈顶元素
  46. 	if(-1==S.top)
  47. 		return false;
  48. 	x=S.data[S.top];
  49. 	return true;
  50.     }

四、循环队列

循环队列是将顺序队列臆造为一个环状空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

顺序队列结点类型描述如下：

  1.     //队列可以用数组也可用链表实现 
  2.     #define MaxSize 5
  3.     typedef int ElemType;
  4.     typedef struct{
  5. 	    ElemType data[MaxSize];
  6. 	    int front,rear;
  7.     }SqQueue;
  8.  
  9.     void InitQueue(SqQueue &Q) {
  10.     //初始化
  11. 	    Q.rear=Q.front=0;
  12.     }
  13.  
  14.     bool isEmpty(SqQueue &Q) {
  15.     //判队空
  16. 	    if(Q.rear==Q.front)
  17. 		    return true;
  18. 	    else	
  19. 		    return false;
  20.     } 
  21.  
  22.     bool EnQueue(SqQueue &Q,ElemType x){
  23.     //入队
  24. 	    if((Q.rear+1)%MaxSize==Q.front)
  25. 		    return false;
  26. 	    Q.data[Q.rear]=x;
  27. 	    Q.rear=(Q.rear+1)%MaxSize;
  28. 	    return true;
  29.     }
  30.  
  31.     bool DeQueue(SqQueue &Q,ElemType &x){
  32.     //出队
  33. 	    if(Q.rear==Q.front)
  34. 		    return false;
  35. 	    x=Q.data[Q.front];
  36. 	    Q.front=(Q.front+1)%MaxSize; 
  37. 	    return true;
  38. }

链式队列描述如下：

  1.     typedef int ElemType;
  2.     typedef struct LinkNode{
  3. 	    ElemType data;
  4. 	    struct LinkNode *next;
  5.     }LinkNode;
  6.     typedef struct{
  7. 	    LinkNode *front,*rear;
  8.     }LinkQueue;
  9.       
  10.     void InitQueue(LinkQueue &Q){
  11.     //初始化
  12. 	    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
  13. 	    Q.front->next=NULL; 
  14.     }
  15.  
  16.     bool IsEmpty(LinkQueue &Q){
  17.     //判队空
  18. 	    if(Q.front==Q.rear)
  19. 		    return true;
  20. 	    else
  21. 		    return false;
  22.     }
  23.  
  24.     void EnQueue(LinkQueue &Q,ElemType x){
  25.     //入队
  26. 	    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
  27. 	    s->data=x;s->next=NULL;
  28. 	    Q.rear->next=s;
  29. 	    Q.rear=s;
  30.     }
  31.  
  32.     bool DeQueue(LinkQueue &Q,ElemType &x){
  33.     //出队
  34. 	    if(Q.front==Q.rear) return false;
  35. 	    LinkNode *p=Q.front->next;
  36. 	    x=p->data;
  37. 	    Q.front->next=p->next;
  38. 	    if(Q.rear==p)
  39. 		    Q.rear=Q.front;
  40. 	    free(p);
  41. 	    return true;
  42.     }

五、二叉树

  1.      //链式存储
  2.      typedef struct BiNode
  3.      {
  4.          char data;
  5.          struct BiTNode *lchild,*rchild;
  6.       }BiNode,*BiTree;
  7.      //前中后序遍历
  8.     void Inorder(BiTree T){
  9.         if(T == NULL) return ;
  10.         Inorder(T->lchild);
  11.         // visit(T->data);
  12.         printf("%c ", T->data);
  13.         Inorder(T->rchild);
  14.     }
  15.  
  16.     void preorder(BiTree T){
  17.         if(T == NULL) return ;
  18.         // visit(T->data);
  19.         printf("%c ", T->data);
  20.         Inorder(T->lchild);
  21.         Inorder(T->rchild);
  22.     }
  23.  
  24.     void postorder(BiTree T){
  25.         if(T == NULL) return ;
  26.         Inorder(T->lchild);
  27.         Inorder(T->rchild);
  28.         // visit(T->data);
  29.         printf("%c ", T->data);
  30.     }    
  31.     //层次遍历
  32.     void leverorder(BiTree BT){
  33.         InitQueue(Q);
  34.         BiTree P;
  35.         EnQueue(Q,BT);
  36.         while(!IsEmpty(Q){
  37.             DeQueue(Q,P);
  38.             visit(P);
  39.             if(p->lchild!=NULL)
  40.                 EnQueue(Q,p->lchild);
  41.             if(p->rchild!=NULL)
  42.                 EnQueue(Q,p->rchild);
  43.             }
  44.         }   
  45.     }
  46.     //非递归
  47.     void inorder(BiTree T){
  48.         InitStack(S);
  49.         BiNode *p = T;
  50.         while(!StackEmpty(S) || p){
  51.             if(!p) {
  52.                 Push(S, p);
  53.                 p = p->lchild;
  54.             }else {
  55.                 Pop(S, p);
  56.                 printf("%c ", p->data);
  57.                 p = p->rchild;
  58.             }
  59.         }
  60.     }
  61.  
  62.     void postorder(BiTree T){
  63.         InitStack(S);
  64.         BiNode *p = T, *last = NULL;
  65.     while(!StackEmpty(S) || p){
  66.         if(p){
  67.             Push(S, p);
  68.             p = p->lchild;
  69.             }
  70.             else {
  71.                 GetTop(S, p);
  72.                 if(p->rchild && p == last){ // 向右子树 递归
  73.                     Pop(S, p);
  74.                     printf("%c ", p->data);
  75.                     last = p;
  76.                     p = NULL;
  77.                 }else {
  78.                     p = p->rchild;
  79.                 }
  80.             }
  81.         }
  82.     }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/391764
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号