时间戳

首页 > 技术文章 > 数据结构复习（一）

数据结构复习（一）

hly97 2020-01-06 21:07 原文

一、数据结构与算法

　　时间复杂度O(n)

　　空间复杂度

二、顺序表及其应用：

  • 顺序查找算法：从顺序表的一端开始顺序扫描，将给定的k值一次与顺序表中各元素的关键字比较
int SeqSearch(List L,KeyType k)
{
    //在顺序表L中顺序查找其关键字等于k的元素，若找到返回该元素的位置，否则为0 
    L.r[0].key=k;    //0号单元做为监视哨 
    int i=L.lengrh;
    while(L.r[i].key!=k)
        i--;
    retutn i;
 }

　　ASL=(求和公式1到n)PiCi = (n+1)/2

  • 二分查找算法(折半查找):要求待查找的数据元素必须按关键字的大小有序排列的顺序表
int BinSrch(List *L,KeyType k)
{
	//在顺序表L中二分查找其关键字等于k的元素，若找到返回该元素的位置 
	int low,high,mid,i;
	low=i=0;
	high=L->length-1;	//置区间初值 
	while(low<=high)
	{
		mid=(low+high)/2;
		if (k == L->r[mid].key)	//找到待查元素 
		{
			i = mid;
			break;
		}
		else if (k < L->r[mid].key)
			high = mid - 1;		//未找到，则在前半去查找 
		else low = mid + 1;		//继续在后半区查找 	
	}
	retutn i;
 }

　　ASL=log2(n+1)-1=log2n

  • 分块查找算法：索引顺序查找，每个索引项记录该块的起始位置，以及该块中的最大关键字(最小)。索引表按关键字有序排列

　　思想：(1)应用二分查找算法或简单顺序查找算法，将给定值key与索引表中的关键字比较，以确定待查元素所在的块

　　　　　(2)应用简单顺序查找算法，在相应块内查找关键字为key的数据元素

　　ASL=log2(n/s+1)+s/2

  • 三种查找算法性能比较：简单顺序查找算法效率最低，其次是分块查找，而二分查找算法的时间性能最好。

 

三、链表及其应用

　　单链表的数据结构

  • 置空表：当单链表为空表时，表中没有任何元素，仅有头结点，即L->next=NULL
  • 求表长：求链表的长度是求链表中不包括头结点在内的结点个数
 1 List *LLsetnull(List *L)    //置空表 
 2 {
 3     L->next=NULL;
 4     return L;
 5 }
 6 List *LLlength(List *L)//求表长 
 7 {
 8     List *p;
 9     p=L->next;
10     int n=0;
11     while(p!=NULL)
12     {
13          n++;
14         p=p->next; 
15     } 
16     return n;17 }
  • 创建单链表头、尾插法：头插法新结点总是插入到头结点之后，尾插法将新结点插入到当前链表的表尾。
 1 LinkList* CreatlistH()    //头插法
 2 {
 3     LinkList* L, * head, * S;
 4     char ch;
 5     L = (LinkList*)malloc(sizeof(LinkList));
 6     head = L;
 7     L->next = NULL;    //建空单链表
 8     ch = getchar();
 9     while (ch != '#')
10     {
11         S= (LinkList*)malloc(sizeof(LinkList));
12         S->data = ch;
13         S->next = L->next;
14         L->next = S;
15         ch = getchar();
16     }
17     return head;
18 }
19 LinkList* CreatlistR()        //尾插法
20 {
21     LinkList* L, * R, * S;
22     char ch;
23     L = (LinkList*)malloc(sizeof(LinkList));
24     L->next = NULL;    //建空单链表
25     R = L;
26     while (ch != '#')
27     {
28         S = (LinkList*)malloc(sizeof(LinkList));
29         S->data = ch;
30         S->next = NULL;        //申请结点并赋值
31         R->next = S;
32         R = S;
33         ch = getchar();
34     }
35     return L;
36 }
  • 插入、删除、查找：
 1 LinkList* Locate(LinkList* L, DataType x)    //单链表按值查找算法
 2 {//在带头结点的单链表L中查找其结点值等于x的结点，找到返回p否则为空
 3     LinkList* p;
 4     p = L->next;    //从第一个结点比较
 5     while (p != NULL)
 6     {
 7         if (p->data != x)
 8             p = p->next;
 9         else break;        //找到，退出循环
10     }
11     return p;
12 }
13 void Linksert(LinkList* L,int i,DataType x)    //在带头结点的单链表L中第i个位置插入值为x的新结点
14 {
15     LinkList* p, * s;
16     int j = 0;
17     p = L;
18     while (p != NULL&&j<i-1)
19     {
20         p = p->next;
21         j++;
22     }
23     if (p == NULL) printf("序号错");
24     else 
25     {
26         s= (LinkList*)malloc(sizeof(LinkList));
27         s->data = x;
28         s->next = p->next;        //不可调换位置
29         p->next = s;
30     }
31 }
32 void Ldelete(LinkList* L, int i)    //在带头结点的单链表L中删除第i个结点
33 {
34     LinkList* p, * s;
35     int j = 0;
36     p = L;
37     while (p != NULL && j < i - 1)
38     {
39         p = p->next;
40         j++;
41     }        //先找到第i-1个结点的存储位置，使指针p指向它
42     if (p != NULL && p->next != NULL)    //第i-1个结点和第i个结点均存在
43     {
44         s = p->next;    //s指向要删除的位置
45         p->next = s->next;
46         free(s);    //释放空间
47     }
48 }

 

四、堆栈及其应用

  • 定义：先进后出，入栈出栈都是在栈顶进行操作。
  • 顺序栈置空：top为0表示还有一个元素只有为-1才是空栈
1 SeqStack* InitStack(SeqStack* S)    //置空，top=-1表示栈空
2 {
3     S->top = -1;
4     return S;
5 }
  • 顺序栈入栈、出栈：栈顶位置top所指示的元素为栈顶元素
 1 void Push(SeqStack* S,DataType x)    //入栈
 2 {
 3     if (S->top <= maxlen - 1 && S->top >= 0)
 4     {
 5         S->top++;
 6         S->data[S->top] = x;
 7     }
 8     else printf("error");
 9 }
10 void Pop(SeqStack* S)    //出栈
11 {
12     if (S->top >= 0)
13         S->top--;
14     else printf("error");
15 }
  • 链栈置空、入栈、出栈：LS为栈顶指针
 1 LinkStack* Push(LinkStack* LS,DataType x)    //入栈
 2 {
 3     LinkStack* p;
 4     p = (LinkStack*)malloc(sizeof(LinkStack * LS));
 5     p->data = x;
 6     p->next = LS;　　//将该结点插入到链栈头部
 7     LS = p;
 8     return LS;
 9 }
10 LinkStack* Pop(LinkStack* LS)//出栈
11 {
12     LinkStack* u;
13     u = LS;
14     LS = u->next;
15     free(u);
16     return LS;
17 }
18 LinkStack* InitStack(LinkStack* LS)    //置空栈
19 {
20     while (LS != NULL)
21         LS=Pop(LS);　　//依次出栈
22     return LS;
23 }

 

五、队列及其应用

  • 循环队列：入队、出队、队空、队满：先进先出
 1 int Full(Queue* Q)
 2 {
 3     if (Q->front == (Q->rear + 1) % max) return 1;
 4     else return 0;
 5 }
 6 int Empty(Queue* S)
 7 {
 8     if (S->front == S->rear) return 1;
 9     else return 0;
10 }
11 void Add(Queue* L, int x)
12 {
13     if (!Full(L))　　//若队不满则入队
14     {
15         L->rear = (L->rear + 1) % max;
16         L->data[L->rear] = x;
17     }
18     else printf("队满");
19 }
20 void Delete(Queue* Q)
21 {
22     if (!Empty(Q))　　//弱队不空则出队
23         Q->front = (Q->front + 1) % max;
24     else printf("队空");
25 }
  • 链队列：设计头指针尾指针
 1 int Empty(LinkQueue* q)
 2 {
 3     if (q->front == q->rear) return 1;
 4     else return 0;
 5 }
 6 LinkQueue* Add(LinkQueue* L, int x)    //将元素x入队列
 7 {
 8     Link* p;
 9     p= (Link*)malloc(sizeof(Link));    //建立新结点存放x
10     p->data = x;
11     p->next = NULL;        //尾插法
12     L->rear->next = p;
13     L->rear = p;
14     return L;
15 }
16 LinkQueue* Delete(LinkQueue* S)
17 {
18     Link* p;
19     if (!Empty(S))        //队不空出队
20     {
21         p = S->front->next;
22         S->front->next = p->next;
23         if (p->next == NULL)    //如果队的长度为1则改变队尾指针
24             S->rear = S->front;
25         free(p);
26         return S;
27     }
28     else printf("队空");
29 }

推荐阅读