头插法建立单链表
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <math.h>
#define OVERFLOW 0
#define OK 1

//head insert to create a list
//头插法建立链表自动就是逆序的

typedef struct student
{
    int num;
    struct student *next;
}node,*slist;

slist head_insert(int n)
{
    slist h = (slist)malloc(sizeof(node));
    h->next = NULL;
    slist s,p;
    s = NULL;
    int a;
    printf("Please input integers:\n");
    while( n-- )
    {
        p = (slist)malloc(sizeof(node));
        scanf("%d", &a);
        p->num = a;
        p->next = s;
        s = p;
        h->next = s;
    }
    return h;
}


int main()
{
    int n;
    printf("input the counts:\n");
    scanf("%d", &n);

    slist hh;
    hh = head_insert(n)->next;

    while(hh != NULL)
    {
        printf("%d ", hh->num);
        hh = hh->next;
    }
    return 0;
}

/*使用头插法建立单链表，并返回指向单链表的头结点的指针*/
Node *CreateAtHead(DataType a[],int n)
{
    int i;
    /*********Begin************/
	struct Node*p,*head;
	head=(struct Node*)malloc(sizeof(struct Node));
	head->next=NULL;
	for(int i=0;i<n;i++){
		p=(struct Node*)malloc(sizeof(struct Node));
		p->data=a[i];
		p->next=head->next;
		head->next=p;
	}
	return head;
    /*******End**************/
}

头插法建立单链表的算法
实现代码：
#include <iostream>  
#include <stdlib.h>  
using namespace std;  
#define maxSize 100  
typedef struct LNode{  
    int data;  
    struct LNode *next;  
}LNode;  
void createListR(LNode *&C,int a[],int n){  
     LNode *s,*r;  
     int i;  
     C=(LNode*)malloc(sizeof(LNode));  
     C->next=NULL;  
     r=C;  
     for(i=1;i<=n;++i){  
        s=(LNode *)malloc(sizeof(LNode));  
        s->data=a[i];  
        s->next=r->next;
        r->next=s;
    }  
}   
int main(int argc, char *argv[])  
{  
    int a[10],e;  
    LNode *C;  
    cout<<"输入九个数：";  
    for(int i=1;i<=9;i++){  
        cin>>a[i];  
    }  
    createListR(C,a,9);  
    cout<<"输入单链表：";  
    for(int i=1;i<=9;++i){  
        C=C->next;  
        cout<<C->data<<" ";  
     }   
    return 0;  
}  
输出结果：
输入九个数：1 3 4 2 5 6 7 8 9
输入单链表：9 8 7 6 5 2 4 3 1 请按任意键继续. . .

目录

1、采用头插法建立单链表

2、尾插法建立单链表

3、按序号查找结点值

4、按值查找表结点

5、插入结点操作

6、删除操作

7、求表长

本篇博客的结点数据结构如下：

typedef struct LNode
 
{
    ElemType data;
 
    struct LNode *next;
 
}LNode,*LinkList;
 

1、采用头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。如图9-1所示



                                                     图9-1  头插法建立单链表

头插法建立单链表的代码如下：

#include <iostream>

using namespace std;

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode, *LinkList;


LinkList List_HeadInsert(LinkList &L)
{
    int data;
    cout << "请输入元素值：" ;
    cin >> data;
    while(data != 10086)
    {
        LNode *node = new LNode();
        node->data = data;
        node->next = L->next;
        L->next = node;
        node = NULL;
        cout << "请输入元素值(10086表示结束)：";
        cin >> data;
    }
    return L;
}

int main()
{
    LNode headNode;
    headNode.next = NULL;
    LinkList L;
    L = &headNode;
    List_HeadInsert(L);
    return 0;
}

输入：



运行结果：



2、尾插法建立单链表

尾插法和头插法的区别在于，头插只需要在头结点之后插入就行，而尾插要依次遍历完链表，找到最后一个结点，插在它的后面（即找到结点next为空的那个结点，然后next指针指向新插入的结点）

尾插法建立单链表的代码如下：

#include <iostream>

using namespace std;

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode, *LinkList;

LinkList List_TailInsert(LinkList &L)
{
    L = new LNode;
    L->next = NULL;

    int data;
    LinkList pTail = L;  //用来指向链表最后一个结点的指针
    cout << "请输入元素值：";
    cin >> data;
    while (data != 10086)
    {
        LNode *node = new LNode();
        node->data = data;
        pTail->next = node;
        pTail = pTail->next;
        node = NULL;
        cout << "请输入元素值(10086表示结束)：";
        cin >> data;
    }
    return L;
}

int main()
{
    LinkList L;
    List_TailInsert(L);
    return 0;
}

输入：



运行结果：



3、按序号查找结点值

从单链表的第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域（NULL），

这个时候就体现了前面说的头结点里存放链表长度的好处了。

代码：

#include <iostream>

using namespace std;

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode, *LinkList;

LinkList List_TailInsert(LinkList &L)
{
    L = new LNode;
    L->next = NULL;

    int data;
    LinkList pTail = L;  //用来指向链表最后一个结点的指针
    cout << "请输入元素值：";
    cin >> data;
    while (data != 10086)
    {
        LNode *node = new LNode();
        node->data = data;
        pTail->next = node;
        pTail = pTail->next;
        node = NULL;
        cout << "请输入元素值(10086表示结束)：";
        cin >> data;
    }
    return L;
}

LNode *GetElem(LinkList L, int i) 
{
    L = L->next;
    int j = 0;
    while (L) 
    {
        j++;
        if (j == i)
            return L;
        L = L->next;
    }
    return NULL;
}

int main()
{
    LinkList L;
    List_TailInsert(L);
    LinkList p = GetElem(L,2);
    return 0;
}

输入：



运行结果：



写完全代码太浪费时间了，后面只写操作的主要代码

4、按值查找表结点

从单链表的第一个结点开始，由前往后依次比较表中各结点的数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针，若整个单链表中都没有这样的结点，则返回NULL。

算法如下：

LNode *LocateElem(LinkList L, ElemType e) 
{
    L = L->next;
    while (L && L->data != e)
        L = L->next;
    return L;        
}

5、插入结点操作

链表p上的结点a和b之间



s->next = p->next;

p->next = s;

6、删除操作



q = p->next;

p ->next = q->next;

free(q);

7、求表长

顺次遍历，记得不要把头结点算进去就行

 

 

人，总是要有一点精神的，不是吗