Chinaunix首页 | 论坛 | 博客
  • 博客访问: 750194
  • 博文数量: 231
  • 博客积分: 3217
  • 博客等级: 中校
  • 技术积分: 2053
  • 用 户 组: 普通用户
  • 注册时间: 2011-07-04 12:01
文章分类

全部博文(231)

文章存档

2015年(1)

2013年(10)

2012年(92)

2011年(128)

分类: C/C++

2012-09-17 09:32:22

说来惭愧,不是计算机专业出身,发现本科没有数据结构,研究生阶段忙着做一些其他的东西,最基础的课程反而没有理解,现在找工作很多笔试需要数据结构,静下心来好好学习一下数据结构。希望别的同学以后搞嵌入式的时候有时间学习一下数据结构和算法,这对你的编程很有好处。
 
常见的时间复杂度大小排列:
O(1)
 
线性表定义:

点击(此处)折叠或打开

  1. #define MAXSIZE 20
  2. typedef int ElemType;
  3. typedef struct
  4. {
  5. ElemType data[MAXSIZE]; /*数组存储数据元素,最大为MAXSIZE*/
  6. int length;}SqList;
获取元素操作:

点击(此处)折叠或打开

  1. #define OK 1
  2. #define ERROR 0
  3. #define TRUE 1
  4. #define FALSE 0
  5. typedef int Status;
  6. Status GetElem(SqList L,int i,ElemType *e)
  7. {
  8. if(L.length==0 || i<1 || i>L-length)
  9. return ERROR;
  10. *e=L.data[i-1];
  11. return OK;
  12. }
插入元素:

点击(此处)折叠或打开

  1. Status ListInsert(SqList *L,int i,ElemType e)
  2. {
  3. int k;
  4. if(L->length==MAXSIZE)
  5. return ERROR;
  6. if(i<1 || i>L-length+1)
  7. return ERROR;
  8. if(i<=L->length)
  9. {
  10. for(k=L->length-1;k>i=i-1;k--)
  11. L->data[k+1]=L->data[k];/*将插入位置后数据元素向后移动一位*/
  12. }
  13. L->data[i-1]=e;
  14. L->length++;
  15. return OK;
  16. }
删除元素:

点击(此处)折叠或打开

  1. Status ListDelete(SqList *L,int i,ElemType *e){
  2. int k;
  3. if(L->length==0) //线性表为空
  4. return ERROR;
  5. if(i<1 || i>L->length)
  6. return ERROR;
  7. *e=L->data[i-1];
  8. if(i<L->length){
  9. for(k=i;k<L->length;k++)
  10. L->data[k-1]=L->data[k];
  11. }
  12. L->length--
  13. return OK;
  14. }
线性表平均时间复杂度为O(n),在读入或则存储时复杂度为O(1),在插入或者删除时时间复杂度为O(n)

单链表定义:

点击(此处)折叠或打开

  1. typedef struct Node{
  2. ElemType data;
  3. struct Node *next;
  4. }Node;
  5. typedef struct Node *LinkList;

结点由存放数据元素的数据域和存放结点的指针域组成,假设p是指向线性表第i个元素的指针,p->data表示一个数据元素,p->next表示第i+1个元素的指针。

获得链表元素:


 

点击(此处)折叠或打开

  1. Status GetElem(LinkList L,int i,ElemType *e)
  2. {
  3. int j;
  4. LinkList p;
  5. p=L->next;
  6. j=1;
  7. while(p && j<i)
  8. {
  9. p=p->next;
  10. ++j;
  11. }
  12. if(!p || j>i)
  13. return ERROR;
  14. *e=p->data;
  15. return OK;
  16. }
单链表插入:
1、声明一个结点p指向链表头结点,促使花j从1开始
2、当j
3、若链表末尾p为空,则说明第i个元素不存在
4、否则查找成功,在系统中生成一个空结点s;
5、将数据元素e赋值给s->data;
6、单链表插入标准语句s->next=p->next;p->next=s(不能反过来,反过来后将p->next给覆盖成s的地址,那么s->next=p->next其实就是s->next=s)
7返回成功

点击(此处)折叠或打开

  1. Status ListInsert(LinkList *L,int i,ElemType e)
  2. {
  3. int j;
  4. LinkList p,s;
  5. p=*L;
  6. j=1;
  7. while(p &&j<i)
  8. {
  9. p=p->next;
  10. ++j;
  11. }
  12. if(!p || j>i)
  13. return ERROR;
  14. s=(LinkList)malloc(sizeof(Node));//生成新节点
  15. s->data=e;
  16. s->next=p->next;
  17. p->next=s;
  18. return OK;
  19. }
单链表删除步骤:
1、声明一个结点p指向链表第一个结点,初始化j从1开始
2、当j
3、若到链表末尾p为空,则说明第i个元素不存在
4、否则查找成功,将欲删除的结点p->next赋值给q;
5、单链表的删除标准语句:p->next=q->next
6、将q结点中的数据赋值给e作为返回
7、释放q结点
8、返回成功

点击(此处)折叠或打开

  1. Status ListDelete(LinkList *L,int i,ElemType *e)
  2. {
  3. int j;
  4. LinkList p,q;
  5. p=*L;
  6. j=1;
  7. while(p->next && j<i)
  8. {
  9. p=p->next;
  10. ++j;
  11. }
  12. if(!(p->next) || j>i)
  13. return ERROR;
  14. q=p->next;
  15. p->next=q->next;
  16. *e=q->data;
  17. free(q);
  18. return OK;
  19. }

单链表的整表创建算法思路:
1、声明一个结点p和计数变量i
2、初始化一空链表L
3、让L的头结点的指针指向NULL,即建立一个带头结点的单链表。
4、循环:生成一新结点赋值给p;随机生成一数字赋值给p的数据域p->data;将p插入到头结点与前结点之间。

点击(此处)折叠或打开

  1. /*随机产生n个元素的值,建立带表头结点的单链表线性表L(头插法)*/
  2. void CreateListHead(LinkList *L,int n){
  3. LinkList p;
  4. int i;
  5. srand(time(0));
  6. *L=(LinkList)malloc(sizeof(Node));//建立一个带头结点的单链表
  7. (*L)->next=NULL;
  8. for(i=0;i<n;i++)
  9. {
  10. p=(LinkList)malloc(sizeof(Node));
  11. p->data=rand()%100+1;
  12. p->next=(*L)->next;
  13. (*L)->next=p;
  14. }
  15. }
插队的办法就是让新结点始终在第一的位置,称为头插法。
每次把新结点都在终端结点的后面称为尾插法。

点击(此处)折叠或打开

  1. /*随机产生n个元素的值,建立带表头结点的单链表现行表L(尾插法)*/
  2. void CreateListTail(LinkList *L,int n)
  3. {
  4. LinkList p,r;
  5. int i;
  6. srand(time(0));
  7. *L=(LinkList)malloc(sizeof(Node));
  8. r=*L;//r指向尾部的结点
  9. for(i=0;i<n;i++)
  10. {
  11. p=(Node *)malloc(sizeof(Node));
  12. p->data=rand()%100+1;
  13. r->next=p;//将表尾端结点的的指针指向新结点
  14. r=p;//将当前的新结点定义为尾端结点
  15. }
  16. r->next=NULL;//表示当前链表结束
  17. }
单链表的整表删除:
1、声明一个结点p和q
2、将第一个结点赋值pxunhuan:释放p;将q赋值给p

点击(此处)折叠或打开

  1. Status ClearList(LinkList *L)
  2. {
  3. LinkList p,q;
  4. p=(*L)->next;//p指向第一个结点
  5. while(p)
  6. {
  7. q=p->next;
  8. free(p);
  9. p=q;
  10. }
  11. (*L)->next=NULL;//头结点指针域为空
  12. return OK;
  13. }

将单链表中终端结点的指针端由空指针改为指向头结点,就是整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表
循环链表和单链表主要差异在于判断p->next是否为空,单链表p->next为空结束,循环链表p->next头结点结束。
双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。所以在每个双向链表中的结点独有两个指针域,一个指向直接后继,一个指向直接前驱。

点击(此处)折叠或打开

  1. typedef struct DulNode
  2. {
  3. ElemType data;
  4. struct DulNode *prior;//直接前驱指针
  5. struct DulNode *next;//直接后继指针
  6. }DulNode,*DulLinkList;
假设元素e的结点是s,要显示将结点s插入到结点p和p->next之间需要执行:
s->prior=p;//把p赋值给s的前驱
s->next=p->next;//把p->next赋值给s的后继
p->next-prior=s;//把s赋值给p->next的前驱
p->next=s;//把s赋值给p的后继
 
假设删除结点p:
p->prior->next=p->next;//把p->net赋值给p->prior的后继
p->next->prior=p->prior;//把p->prior赋值给p->next的前驱
free(p);

 







阅读(896) | 评论(0) | 转发(0) |
0

上一篇:shell do...done < $config

下一篇:排序

给主人留下些什么吧!~~