数据结构与算法（二）

1.线性表——链表结构与顺序存储结构优缺点对比

存储分配方式：

• 顺序存储结构⽤⽤⼀段连续的存储单元依次存储线性表的数据元素

• 单链表采⽤链式存储结构,⽤⼀组任意的存储单元存放线性表的元素

时间性能:

• 查找

• 顺序存储 O(1)

• 单链表O(n)

• 插⼊和删除

• 存储结构需要平均移动⼀个表⻓⼀半的元素,时间O(n)

• 单链表查找某位置后的指针后,插⼊和删除为 O(1)

空间性能:

• 顺序存储结构需要预先分配存储空间,分太⼤,浪费空间;分⼩了,发⽣上溢出

• 单链表不需要分配存储空间,只要有就可以分配, 元素个数也不受限制

2.线性表——循环链表

image

2.1 循环链表的初始化及赋值


#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

2种情况:① 第一次开始创建; ②已经创建,往里面新增数据

判断是否第一次创建链表

YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);

NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);


Status CreateList(LinkList *L){

    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("输入节点的值，输入0结束\n");
    while(1)
    {
        scanf("%d",&item);
        if(item==0) break;
        
          //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己  (*head)->next=*head;
        if(*L==NULL)
        {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L)exit(0);
            (*L)->data=item;
            (*L)->next=*L;
        }
        else
        {
           //输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
            
            for (target = *L; target->next != *L; target = target->next);
            
            temp=(LinkList)malloc(sizeof(Node));
            
            if(!temp) return ERROR;
            
            temp->data=item;
            temp->next=*L;  //新节点指向头节点
            target->next=temp;//尾节点指向新节点
        }
    }
    
    return OK;
}

优化方案：设置一个指针r 指向最后一个节点


Status CreateList2(LinkList *L){
    
    int item;
    LinkList temp = NULL;
    LinkList r = NULL;
    printf("请输入新的结点, 当输入0时结束!\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) {
            break;
        }
        
        //第一次创建
        if(*L == NULL){
            
            *L = (LinkList)malloc(sizeof(Node));
            if(!*L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
            r = *L;
        }else{
            
            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return  ERROR;
            temp->data = item;
            temp->next = *L;
            r->next = temp;
            
            r = temp;
        }
        
    }
    
    return OK;
}

2.2 遍历循环链表

循环链表的遍历最好用do while语句，因为头节点就有值


void show(LinkList p) {
    //如果链表是空
    if(p == NULL){
        printf("打印的链表为空!\n");
        return;
        
    }else{
        LinkList temp;
        temp = p;
        do{
            printf("%5d",temp->data);
            temp = temp->next;
        }while (temp != p);
        printf("\n");
    }
    
}

2.3 循环链表插入数据