数据结构与算法之单链表C语言实现

1.头结点和头指针区别 2.结构指针描述单链表 3.获取第i个元素 4.第i个位置插入元素 5. 删除第i个元素 6. 头插法创建单链表 7. 尾插法创建单链表

1.头结点和头指针区别

头指针: 指向链表第一个结点的指针,如果链表有头结点,则指向头结点,无论链表是否为空,头指针均不为空,头指针是链表的必要元素 头结点: 为了操作的统一和方便而设立的,放在第一个结点之前,数据域一般无意义,有了头结点在对第一个结点前插入和删除第一个结点的操作就和其他结点的操作统一了

2.结构指针描述单链表

#include 
#include 

typedef int elemtype;


typedef struct node{
    elemtype data;//数据域
    struct node *next;//指针域
} node;

typedef struct node *linklist;

3.获取第i个元素

//p是个指向node的指针,p->next指向下一个结点的指针:所以下一个结点的数据域就是p->next->data,指针域就是p->next->next
//指针和结构体访问成员变量,结构体使用.而指针使用->
int getelem(linklist l, int i, elemtype *e){
    int j;
    linklist p;
    p = l->next;//这里l代表投指针,l->next可能是头结点,也可能是第一个结点
    j = 1;
    while (p && j < i) {//迭代遍历
        p = p->next;
        j++;
    }
    if (!p || j > i) { //p=null或者超过了i,没找到
        return 0;
    }
    *e = p->data;
    return 1;
}

4.第i个位置插入元素

int listinsert(linklist *l,int i, elemtype e){
    int j = 1;
    linklist p,s;
    p = *l;//l->next二者的区别?
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }

    s = (linklist)malloc(sizeof(node));
    s->data = e;
    s->next = p->next;

    p->next = s;
    return 0;
}

5. 删除第i个元素

int listdelete(linklist *l, int i, elemtype *e){
    int j = 1;
    linklist p,s;
    p = *l;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }

    s = p->next;//先把第i个结点保存下来,以便释放
    p->next = s->next;//s->next就是p->next->next
    *e = s->data;
    free(s);
    return 1;
}

6. 头插法创建单链表

void createlisthead(linklist *l, int n){
    linklist p;
    int i;
    *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;
    }

}

7. 尾插法创建单链表

//r作为动态指针,依次往下移动
void createlisttail(linklist *l,int n){
    linklist p,r;
    int i;
    *l = (linklist)malloc(sizeof(node));//头结点-->表头
    r = *l;//r指向头结点

    for (i = 0; i < n; i++) {
        p = (linklist)malloc(sizeof(node));//新节点
        p->data = rand() % 100 + 1;
        r->next = p;//头结点指向新建的p结点
        r = p;//移动r指针指向,有r=*l头结点,变成r=p指向p结点
    }
    r->next = null;//等同于p->next=null
}