单链表

程序构思:

单链表的建立

(1) 先建立头结点head，将头结点的指针域置为空。

(2) 新建一个指向头结点的指针m，即node *m = head;（首端插入方式不需要该步骤）。

(3) 新建一个结点p，把此新结点链接到单链表的尾端（p->next设为空）或者始端。

1⃣️首端插入方式

​ ①p->next指向头结点指向的下一个结点head->next。

​ ②head->next指向p。

2⃣️尾端插入方式。

​ ①m->next指向p，即m->next = p;

​ ②把指针p赋值给m，也就是说每次m都要最终指向新插入的结点。m = p;

单链表的插入

(1) 新建一个结点p，指定插入位置。

(2) 从单链表开始查找结点位置。

​ ①找到该位置，则p->next指向当前位置的下一个结点，当前位置结点指向新建结点p。

​ ②没有找到该位置，插入操作失败。

单链表的删除

(1) 指定删除位置。

(2) 链表头开始找到结点位置。

​ ①找到该位置，则删除该位置的结点。

​ ②没有找到该位置，删除操作失败。

示例代码

#include <iostream>
#include <stdlib.h>
#include <cstdio>
using namespace std;
 
 
 
typedef int elementtype;    //指定单链表中数据类型
 
//单链表存储结构定义
typedef struct node
{
    elementtype data;  //数据域
    struct node *next; //指针域
}*linklist;
 
#pragma mark - 建立一个空线性表/单链表(方法一)
/****----------------------------------------------****/
//单链表建立方法一(函数用返回值得到表头指针)
//函数名: createone(int n)
//参数:  (传入)int n, 传入线性表结点数量
//作用: 建立一个空线性表
//返回值:node *型返回结构体指针,即得到建立的线性表头指针
/****---------------------------------------------****/
 
node* createone(int n)
{
    int i;
    node *head;  //定义头结点指针
    node *p;     //定义新结点指针
    
    //建立带头结点的线性链表
    head = (node*)malloc(sizeof(node));
    head->next = null;
    
    cout << "please input the data for linklist nodes:" << endl;
    
    /** 该链表创建并初始化采用的是从表尾插入n个元素,比如如果输入的是:1 2 3,那么输出链表时会输出3 2 1 */
    /*
    for (i = n; i > 0; i--) {
        p = (node*)malloc(sizeof(node));   //为新结点申请空间,即创建一个新结点
        scanf("%d", &p->data);  //新结点赋值
        //新结点插入到表头
        p->next = head->next;
        head->next = p;
    }
     */
    
    /** 该链表创建并初始化采用的是从表头插入n个元素,比如输入的是:1 2 3, 那么输出的顺序也是会: 1 2 3 */
    node *tempnode = head;
    for (i = n; i > 0; i--) {
        p = (node*)malloc(sizeof(node));   //为新结点申请空间,即创建一个新结点
        scanf("%d", &p->data);  //新结点赋值
        //新结点插入到表尾
        tempnode->next = p;
        tempnode = p;
    }
    tempnode->next = null;
    return head;   //返回头结点指针,即可以得到单链表的地址
}
 
#pragma mark - 建立一个空线性表/单链表(方法二)
/****----------------------------------------------****/
//单链表建立方法二(函数无返回值)
//函数名: createtwo(node* head, int n)
//参数: (传入)node* head传入一个链表指针
//     (传入)int n,传入线性表结点数量
//作用: 建立一个空线性表
//返回值: 无
/****---------------------------------------------****/
 
void createtwo(node *head, int n)
{
    int i;
    node *p;   //定义新结点指针
    
    //建立带头结点的线性链表
    head = (linklist)malloc(sizeof(node));
    head->next = null;
    
    cout << "please input the data for linklist nodes:" << endl;
    for (i = n; i > 0; i--) {
        p = (node*)malloc(sizeof(node));   //为新结点申请空间,即创建一新结点
        scanf("%d", &p->data);   //为新结点赋值
        
        //新结点插入到表头
        p->next = head->next;
        head->next = p;
    }
}
 
#pragma mark - 向单链表中插入一个元素
/****----------------------------------------------****/
//函数名: insertnode(node *l, int i, elementtype e)
//参数: (传入)node *l,传入线性表头指针l
//     (传入)int i插入位置
//     (传入)elementtype e插入元素
//作用: 线性表中插入一个元素
//返回值: int型,返回1表示操作成功,0表示失败
/****---------------------------------------------****/
int insertnode(node *l, int i, elementtype e)
{
    node *p = l;   //定义一个指向第一个结点的指针
    int j = 0;
    
    //顺指针向后查找, 直到p指向第一个结点
    while (p && j < i) {
        p = p->next;
        j++;
    }
    
    //插入位置合法性判断
    if (!p || j > i) {
        cout << "error! the location is illegal!"  << endl;
        return 0;
    }
    
    node *s;
    s = (node*)malloc(sizeof(node));   //建立新结点
    s->data = e;    //新结点赋值
    
    //插入结点
    s->next = p->next;
    p->next = s;
    return 1;
}
 
#pragma mark - 删除单链表中的一个元素
/****----------------------------------------------****/
//函数名: deletenode(linklist &l, int i, elementtype &e)
//参数: (传入)linklist &l,线性表头指针l的地址
//     (传入)int i删除位置
//     (传出)elementtype &e 存储删除节点元素的值
//作用: 线性表中删除一个元素
//返回值: elementtype型返回删除结点元素的值
/****---------------------------------------------****/
elementtype deletenode(linklist &l, int i, int &e)
{
    node *p;
    p = l;    //定义一个指向第i个结点的指针p
    node *q;  //暂时存放待删除结点
    int j = 0;
    
    //顺指针向后查找,直到p指向第i个结点
    while (p->next && j < i) {
        p = p->next;
        j++;
    }
    
    //删除位置合法性判断
    if (!p || j > i) {
        cout << "element is not exist!";
        return 0;
    }
    
    q = p->next;
    p->next = q->next;  //删除第i个结点
    e = q->data;
    free(q);
    return e;   //返回删除结点元素的值
}
 
#pragma mark - 显示线性表中的所有元素
/****----------------------------------------------****/
//函数名: displaylist(linklist &l)
//参数: (传入)linklist &l,线性表头指针l的地址
//作用: 显示线性表中所有元素
//返回值: 无
/****---------------------------------------------****/
void displaylist(linklist &l)
{
    node *p;
    p = l->next;    //定义一个指向表头结点的指针p
    while (p != null) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
 
#pragma mark - 主函数
int main(int argc, const char * argv[]) {
    node *l1;
    int nodenum;
    printf("please input the init linknode number:\n");
    scanf("%d", &nodenum);
    l1 = createone(nodenum);
    
    //node *l2;
    //createtwo(l2, nodenum);  //也可以这样生成l2链表
    
    //输出当前链表内容
    printf("the current l1 is:");
    displaylist(l1);
    
    //调用
    int result;   //为了判断调用成功与否,可以定义result以备检查
    result = insertnode(l1, 3, 88);
    if (result) {
        printf("success to insert!\n");
    }
    
    elementtype deletenumber;
    deletenode(l1, 0, deletenumber);
    printf("被删除的元素为: %d\n", deletenumber);
    //输出当前链表的内容
    printf("the curent l1 is:");
    displaylist(l1);
    return 0;
}