数据结构和算法学习笔记

时间：2022-04-02 10:24:25

常见的时间复杂度

常用的时间复杂度所耗费的时间从小到大依次是：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

算法的空间复杂度

线性表

数据类型可以分为原子类型和结构类型

Operation

InitList(*L)：初始化操作，建立一个空的线性表L。

ListEmpty(L)：判断线性表是否为空表，若线性表为空，返回true，否则返回false。

ClearList(*L)：将线性表清空。

GetElem(L,i,*e)：将线性表L中的第i个位置元素值返回给e。

LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中表示成功；否则，返回0表示失败。

ListInsert(*L,i,e)：在线性表L中第i个位置插入新元素e。

ListDelete(*L,i,*e)：删除线性表L中第i个位置元素，并用e返回其值。

ListLength(L)：返回线性表L的元素个数。

线性表有两种物理存储结构：顺序存储结构和链式存储结构

顺序结构

#define MAXSIZE 20
typedef int EleType
typedef struct
{
    EleType data[MAXSIZE];
    int length;
}SqList;
ListInsert.c 

/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)。*/
/*操作结果：在L中第i个位置之前插入新的数据元素e，L长度+1*/

Status ListInsert(SqList *L, int i, ElemType e)
{
int k;

if( L->length == MAXSIZE )//顺序线性表已经满了
{
return ERROR;
}
if( i<1 || i>L->length+1)//当i不在范围内时
{
return ERROR;
}
if( i <= L->length )//若插入数据位置不在表尾
{
/*将要插入位置后数据元素向后移动一位*/
for( k=L->length-1; k >= i-1; k-- )
{
L->data[k+1] = L->data[k];
}
}

L->data[i-1] = e;//将新元素插入
L->length++;

return OK;
}
单链表存储结构

C语言可以用结构指针来描述单链表

typedef struct Node
{
ElemType data;//数据域
struct Node* Next;//指针域
}Node;
typedef struct Node* LinkList;
/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)。*//*操作结果：用e返回L中第i个数据元素的值*/Status GetElem(LinkList L, int i, ElemType *e){int j;LinkList p;p = L->next;j = 1;while( p && j<i ){p = p->next;++j;}if( !p || j>i ){return ERROR;}*e = p->data;return OK;}

ListInsert.c

/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)。*/
/*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/

Status ListInsert(LinkList *L, int i, ElemType e)
{
int j;
LinkList p, s;

p = *L;
j = 1;

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

if( !p || j>i )
{
return ERROR;
}

s = (LinkList)malloc(sizeof(Node));
s->data = e;

s->next = p->next;
p->next = s;

return OK;
}
ListDelete.c 

/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)。*/
/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度-1*/

Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p, q;

p = *L;
j = 1;

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

if( !(p->next) || j>i )
{
return ERROR;
}

q = p->next;
p->next = q->next;

*e = q->data;
free(q);

return OK;
}
CreateListHead.c 

/*头插法建立单链表示例*/

void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;

srand(time(0));

*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;

for( i = 0; i < n; i++ )
{
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100+1;
p->next = (*L)->next;
(*L)->next = p;
}
}

CreateListTail.c

/*尾插法建立单链表示例*/

void CreateListTail(LinkList *L, int n)
{
LinkList p, r;
int i;

srand(time(0));

*L = (LinkList)malloc(sizeof(Node));
r = *L;

for( i = 0; i < n; i++ )
{
p = (Node *)malloc(sizeof(Node));
p->data = rand()%100+1;
r->next = p;
r = p;
}
}

ClearList.c

Status ClearList(LinkList *L)
{
LinkList p, q;

p = (*L)->next;

while(p)
{
q = p->next;
free(p);
p = q;
}

(*L)->next = NULL;

return OK;
}
静态链表 

#define MAXSIZE 1000
typedef struct
{
ElemType data;//数据
int cur;//游标（Cursor）
} Component, StaticLinkList[MAXSIZE];
对静态链表进行初始化相当于初始化数组 

Status InitList(StaticLinkList space)
{
int i;
for( i = 0; i < MAXSIZE-1; i++ )
space[i].cur = i + 1;
space[MAXSIZE-1].cur = 0;
return OK;
}

首先是获得空闲分量的下标

int Malloc_SLL(StaticLinkList space)
{
int i = space[0].cur;
if( space[0].cur )
space[0].cur = space[i].cur;
//把它的下一个分量用来作为备用
return i;
}
ListInsert.c 

/*在静态链表L中第i个元素之前插入新的数据元素e*/

Status ListInsert( StaticLinkList L, int i, ElemType e )
{
int j, k, l;

k = MAX_SIZE - 1;//数组的最后一个元素
if( i<1 || i>ListLength(L)+1 )
{
return ERROR;
}

j = Malloc_SLL(L);
if( j )
{
L[j].data = e;
for( l=1; l<=i-1; l++ )
{
k = L[k].cur;
}
L[j].cur = L[k].cur;
L[k].cur = j;

return OK;
}

return ERROR;
}
/*删除在L中的第i个数据元素*/Status ListDelete(StaticLinkList L, int i){int j, k;if( i<1 || i>ListLength(L) ){return ERROR;}k = MAX_SIZE - 1;for( j = 1; j <= i-1; j++ ){k = L[k].cur;}j = L[k].cur;L[k].cur = L[j].cur;Free_SLL(L, j);return OK;}/*将下标为k的空闲结点回收到备用链表*/void Free_SLL(StaticLinkList space, int k){space[k].cur = space[0].cur;space[0].cur = k;}/*返回L中数据元素个数*/int ListLength(StaticLinkList L){int j = 0;int i = L[MAXSIZE-1].cur;while(i){i = L[i].cur;j++;}return j;}
Status GetMidNode(LinkList L, ElemType *e){LinkList = search , mid;mid = search = L;while(search->next != NULL){/*search移动的速度是mid的2倍*/if(search->next->next !=NULL){search = search->next->next;mid = mid->next;}else{search = search->next;}}*e = mid->data;return OK;}

循环链表

/*初始化循环链表*/
void ds_init(node **pNode)
{
int item;
node *temp;
node *target;

printf("输入结点的值，输入0完成初始化\n");

while(1)
{
scanf("%d", &item);
fflush(stdin);

if(item == 0)
return;

if((*pNode) == NULL)
{
/*循环链表中只有一个结点*/
*pNode = (node*)malloc(sizeof(struct CLinkList));
if(!(*pNode))
exit(0);
(*pNode)->data = item;
(*pNode)->next = *pNode;
}
else
{
/*找到next指向第一个结点的结点*/
for(target = (*pNode); target->next != (*pNode); target = target->next)
;

/*生成一个新的结点*/
temp = (node *)malloc(sizeof(struct CLinkList))

if(!temp)
exit(0);

temp->data = item;
temp->next = *pNode;
target->next = temp;
}
}
}
/*链表存储结构的定义*/typedef struct CLinkList{int data;struct CLinkList *next;}node;/*插入结点*//*参数：链表的第一个结点，插入的位置*/void ds_insert(node **pNode, int i){node *temp;node *target;node *p;int item;int j = 1;printf("输入要插入结点的值：");scanf("%d", &item);if(i == 1){//新插入的结点作为第一个结点temp = (node *)malloc(sizeof(struct CLinkList));if(!temp)exit(0);temp->data = item;/*寻找到最后一个结点*/for(target = (*pNode); target->next != (*pNode); target = target->next);temp->next = (*pNode);target->next = temp;*pNode = temp;}else{target = *pNode;for( ; j < (i-1); ++j ){target = target->next;}temp = (node *)malloc(sizeof(struct CLinkList));if(!temp)exit(0);temp->data = item;p = target->next;target->next = temp;temp->next = p;}}
/*删除结点*/void ds_delete(node **pNode, int i){node *target;node *temp;int j = 1;if(i == 1){//删除的是第一个结点/*找到最后一个结点*/for(target = (*pNode); target->next != (*pNode); target = target->next);temp = *pNode;*pNode = (*pNode)->next;target->next = *pNode;free(temp);}else{target = *pNode;for( ; j < (i-1); ++j ){target = target->next;}temp = target->next;target->next = temp->next;free(temp);}}
/*返回结点所在位置*/int ds_search(node *pNode, int elem){node *target;int i = 1;for(target = pNode; target->data != elem && target->next != pNode; ++i){target = target->next;}if(target->next == pNode)/*表中不存在该元素*/return 0;elsereturn i;}

约瑟夫问题

//n个人围圈报数，报m出列，最后剩下的是几号？
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
int data;
struct node *next;
}node;

node *create(int n)
{
node *p = NULL, *head;
head = (node*)malloc(sizeof(node));
p = head;
node *s;
int i = 1;

if( 0 != n )
{
while( i <= n )
{
s = (node *)malloc(sizeof(node));
s->data = i++;//为循环链表初始化，第一个结点为1，第二个结点为2.
p->next = s;
p = s;
}
s->next = head->next;
}

free(head);

return s->next;
}

int main()
{
int n = 41;
int m = 3;
int i;
node *p = create(n);
node *temp;

m %= n;

while (p != p->next )
{
for(i = 1; i < m-1; i++)
{
p = p->next;
}

printf("%d->", p->next->data);
temp = p->next;//删除第m个结点
p->next = temp->next;

free(temp);

p = p->next;
}

printf("%d\n", p->data);

return 0;
}

链表有环的定义：链表的尾结点指向了链表中的某个节点。

魔术师发牌问题

#include <stdio.h>
#include <stdlib.h>

#define CardNumber 13

typedef struct node
{
    int data;
    struct node *next;
}sqlist, *linklist;

linklist CreateLinkList()
{
    linklist head = NULL;
    linklist s, r;
    int i;

    r = head;

    for(i=1; i<= CardNumber; i++)
    {
        s = (linklist)malloc(sizeof(sqlist));
        s->data = 0;

        if(head == NULL)
            head = s;
        else
            r->next = s;

        r = s;
    }

    r->next = head;

    return head;
}

//发牌顺序计算
void Magician(linklist head)
{
    linklist p;
    int j;
    int Countnumber = 2;

    p = head;
    p->data = 1;    //第一张牌放1

    while(1)
    {
        for(j=0; j < Countnumber; j++)
        {
            p = p->next;
            if(p->data != 0)    //该位置有牌的话，则下一个位置
            {
                p->next;
                j--;
            }
        }

        if(p->data == 0)
        {
            p->data = Countnumber;
            Countnumber++;

            if(Countnumber == 14)
                break;
        }
    }
}

//销毁工作
void DestroyList(linklist* list)
{
    linklist ptr = *list;
    linklist buff[CardNumber];
    int i = 0;

    while(i < CardNumber)
    {
        buff[i++] = ptr;
        ptr = ptr->next;
    }

    for(i=0; i < CardNumber; ++i)
        free(buff[i]);

    *list = 0;
}

int main()
{
    linklist p;
    int i;

    p = CreateLinkList();
    Magician(p);

    printf("按如下顺序排列：\n");
    for(i=0; i< CardNumber; i++)
    {
        printf("黑桃%d ", p->data);
        p = p->next;
    }

    DestroyList(&p);

    return 0;
}

凯瑟问题

#include <stdio.h>
#include <stdlib.h>

#define OK      1
#define ERROR   0

typedef char ElemType;
typedef int Status;

typedef struct DualNode
{
    ElemType data;
    struct DualNode *prior;
    struct DualNode *next;
}DualNode, *DuLinkList;

Status InitList(DuLinkList *L)
{
    DualNode *p, *q;
    int i;

    *L = (DuLinkList)malloc(sizeof(DualNode));
    if(!(*L))
    {
        return ERROR;
    }

    (*L)->next = (*L)->prior = NULL;
    p = (*L);

    for( i=0; i < 26; i++ )
    {
        q = (DualNode *)malloc(sizeof(DualNode));
        if( !q )
        {
            return ERROR;
        }
        q->data = 'A'+i;
        q->prior = p;
        q->next = p->next;
        p->next = q;

        p = q;
    }
    p->next = (*L)->next;
    (*L)->next->prior = p;

    return OK;
}

void Caesar(DuLinkList *L, int i)
{
    if( i > 0 )
    {
        do
        {
            (*L) = (*L)->next;
        }while( --i );
    }

    if( i < 0 )
    {
        do
        {
            (*L) = (*L)->next;
        }while( ++i );
    }
}

int main()
{
    DuLinkList L;
    int i, n;

    InitList(&L);

    printf("请输入一个整数：");
    scanf("%d", &n);
    printf("\n");
    Caesar(&L, n);

    for( i=0; i < 26; i++ )
    {
        L = L->next;
        printf("%c", L->data);
    }
    return 0;
}

栈

typedef struct
{
ElemType *base;
ElemType *top;
int statckSize;
}sqStack;

#define STACK_INIT_SIZE 100
initStack(sqStack *s)
{
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType) );
if( !s->base )
exit(0);
s->top = s->base;//最开始，栈顶就是栈底
s->statckSize = STACK_INIT_SIZE;
}

#define STACKINCREMENT 10

Push(sqlStack *s, ElemType e)
{
//如果栈满，追加空间
if( s->top - s->base >= s->stackSize )
{
s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !s->base )
exit(0);

s->top = s->base + s->stackSize;//设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量
}

*(s->top) = e;
s->top++;
}

Pop(sqStack *s, ElemType *e)
{
if( s->top == s->base )//栈已空
{
return;
}
*e = *--(s->top);
}

DestroyStack(sqStack *s)
{
int i, len;
len = s->stackSize;
for( i=0; i < len; i++ )
{
free( s->base );
s->base++;
}
s->base = s->top = NULL;
s->stackSize = 0;
}

int StackLen(sqStack s)
{
return (s.top - s.base);
}
二进制转十进制 
#include <stdio.h>#include <stdlib.h>#include <math.h>#define STACK_INIT_SIZE 20#define STACKINCREMENT 10typedef char ElemType;typedef struct{ElemType *base;ElemType *top;int stackSize;}sqStack;void InitStack(sqStack *s){s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if( !s->base ){exit(0);}s->top = s->base;s->stackSize = STACK_INIT_SIZE;}void Push(sqStack *s, ElemType e){if( s->top - s->base >= s->stackSize ){s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));if( !s->base ){exit(0);}}*(s->top) = e;s->top++;}void Pop(sqStack *s, ElemType *e){if( s->top == s->base ){return;}*e = *--(s->top);}int StackLen(sqStack s){return (s.top - s.base);}int main(){ElemType c;sqStack s;int len, i, sum = 0;InitStack(&s);printf("请输入二进制数，输入#符号表示结束！\n");scanf("%c", &c);while( c != '#' ){Push(&s, c);scanf("%c", &c);}getchar();//把'\n'从缓冲区去掉len = StackLen(s);printf("栈的当前容量是：%d\n", len);for( i=0; i < len; i++ ){Pop(&s, &c);sum = sum + (c-48) * pow(2, i);}printf("转换为十进制数是：%d\n", sum);return 0;}




























标签：

相关文章