7-1 有序链表的插入（20 分）
 
 
 
 
  
 
   
已知一个递增有序链表L（带头结点，元素为整数），编写程序将一个新整数插入到L中，并保持L的有序性。其中单链表的类型定义参考如下：
 
   
typedef int elementType;
 
   
typedef struct lnode 
 
   
{ elementType data; 
 
   
struct lnode *next; 
 
   
}Lnode,* LinkList;
 
   
输入格式:
 
   
输入分三行
 
   
第一行 元素个数
 
   
第二行 元素的值，元素间用空格分隔。
 
   
第三行 待插入的元素值
 
   
输出格式:
 
   
在一行中输出有序链表元素值，每个元素前输出一个空格以便与相邻元素分隔。
 
   
输入样例:
 
   
5
1 3 5 7 9
4
 
   
输出样例:
 
   
 1 3 4 5 7 9
 
  
 
 
 
 以下为代码： 
 

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

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int Status;
typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;//单链表的结构体定义

Status LinkListCreate_CL(LinkList &CL);
void ListPrint_CL(LinkList CL);
Status LinkListInsert_CL(LinkList &CL,ElemType e);

Status LinkListCreate_CL(LinkList &CL)
{
    LNode *curPtr, *rearPtr;
    CL = (LNode*)malloc(sizeof(LNode));
    if(!CL)
        exit(OVERFLOW);
    CL->next = NULL;
    curPtr = CL;
    rearPtr = CL;
    //头节点的尾指针和当前指针都指向头节点
    int TheNumberOfElement;
    scanf("%d", &TheNumberOfElement);
    for(int i = 0; i < TheNumberOfElement; i++)
    {
        curPtr = (LNode*)malloc(sizeof(LNode));
        if(!curPtr)
            exit(OVERFLOW);
        scanf("%d", &curPtr->data);
        rearPtr->next = curPtr;
        rearPtr = curPtr;//连接节点
    }
    rearPtr->next = NULL;//最后一个节点的尾指针赋空
    return OK;
}
void ListPrint_CL(LinkList CL)
{
    LNode *p = CL->next;
    while(p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
Status LinkListInsert_CL(LinkList &CL,ElemType e)
{
    LNode *curPtr = CL->next, *rearPtr = CL, *temPtr;
    temPtr = (LNode*)malloc(sizeof(LNode));
    if(!temPtr)
        exit(OVERFLOW);
    temPtr->data = e;
    temPtr->next = NULL;
    if(curPtr == NULL)
    {
        rearPtr->next = temPtr;
        temPtr->next = NULL;
        return OK;
    }
    while(curPtr)
    {
        if(curPtr->data >= e)
        {
            rearPtr->next = temPtr;
            temPtr->next = curPtr;
            return OK;
        }
        rearPtr = curPtr;
        curPtr = curPtr->next;
    }
    curPtr->next = temPtr;
    temPtr->next = curPtr;
    return OK;
}

int main()
{
    LinkList CL;
    ElemType elem;
    if(LinkListCreate_CL(CL) != OK)
    {
        printf("InitList_Sq: 初始化失败！！！\n");
        return -1;
    }
    scanf("%d", &elem);
    LinkListInsert_CL(CL,elem);
    ListPrint_CL(CL);
    return 0;
}


 

 
 

 

题目：给定一个整数num，如何在节点有序的环形链表中插入一个节点值为num的节点，并保证这个环形链表依然有序。（假如链表是升序）
 
解决思路：
 1.如果链表为空，则开辟一个节点，让后让他自己指向自己，然后返回该节点。
 2.如果链表不为空，分为三种情况：
 a.如果插入的节点的值是在环形链表最大值和最小的闭区间范围之内，即在链表[min,max]里面，那么先找到要插入的位置，然后插入。
 
 b.如果插入的节点的值大于链表最后一个值，那么插入的位置就直接是最后一个节点的后面，然后让他指向头结点，最后返回头结点。
 
 c.如果插入的节点小于链表的第一个节点，也就是小于最小的一个节点，那么插入的位置还是链表的最后一个节点的后面，然后让他指向头结点，最后返回新插入的节点。
 
 
有了方法，代码就比较好写了。
 
typedef struct node
{
	DataType data;
	struct node *p_next;
}Node ,*PNode;

PNode InsertInCircle(PNode head,DataType data)//插入一个节点在有序链表中，并且插入之后链表有序
{
	//1.如果环形链表是空，则将该节点插入，返回该节点
	if (head == NULL)
	{
		PNode pCur = NULL;
		pCur = (PNode)malloc(sizeof(Node));
		pCur->data = data;
		pCur->p_next = pCur;
		return pCur;
	}
	else
	{
		//2.先找到只要插入的位置
		pCur = head->p_next;
		PNode pPre = head;
		while (pCur != head)
		{
			//a.插入位置在链表内
			if (pPre->data <= data && pCur->data >= data)
			{
				PNode pNode = (PNode)malloc(sizeof(Node));
				pNode->data = data;
				pPre->p_next = pNode;
				pNode->p_next = pCur;
				return head;
			}
			pPre=pPre->p_next;
			pCur = pCur->p_next;
		}
		//.出循环,说明此时data是链表中最大或者是最小的节点
		//此时pCur==head
		PNode pNode = (PNode)malloc(sizeof(Node));
		pNode->data = data; 
		pPre->p_next = pNode;
		//b.比头结点小
		pNode->p_next = pCur;
		if (data < head->data)
			return pNode;
		else
			//比头结点大
			return head;
	}
}
 
结果：
 测试的链表有5个节点，分别是1->2->3->4->5->1(最后的1是多打印了一次原链表只有一个值为1的节点）…
 1.当链表为空
 
 2.插入值为1的节点
 
 3.插入值为2的节点
 
 4.插入值为5的节点
 
 5.插入值为6的节点
 

 测试及源代码下载：源代码

链表的创建查看
 
按特定值插入链表，要求链表本身使用某种排序方法排好序的。
 
 
 
链表的插入分四种情况：
 
1、原链表为空时：使头结点head指向新插入的节点p_new;
 
 
 
2、在第一个节点前加入：使头结点head指向新插入的节点p_new，新插入的节点p_new的next指向第一个节点；
 
3、在中间插入节点：使新加入的节点的前一个节点指向新加入的节点p_new，新加入的节点的next指向前一个节点的next；
 
4、在末尾插入节点：使末尾节点的next指向新插入的节点p_new，p_new的next指向NULL。
 

 //-------------------------------------------------------------
 --1、链表为空：新插入的节点就是头结点
 
 
 

 *p_head = p_new;
 
 p_new->next = NULL;
 
--2、链表不为空：
循环查找，首个节点的num比新来的num大，插入到它的前面
 
 
 
 
 

 1）找到一个节点的num比新来的num大
 
 
 
 
 

  1.找到的节点是头结点，插在最前面
 
 
 
 
  

   p_new->next = pb;
  
 
 
 
 
 
  

   *p_head = p_new;
  
 
 
 
 

  2.插在普通节点的前面（中间位置）
 
 
 
 
  

   pf->next = p_new;
  
 
 
 
 
 
  

   p_new->next = pb;
  
 
 
 
 

 2）没有找到一个节点num，比新来的节点的num大，插在后面
 
 
 

  pb->next=p_new;
 
 
 

  p_new->next = NULL;
 
 
 
//-------------------------------------------------------------
 
结构体节点：
 
 
 
typedef struct student {
    int num;        //学号
    int score;    //分数
    char name[20];
    struct student *next;//指针域
}STU;
 
demo：
 
 
 
void link_insert(STU **p_head, STU *p_new)
{
    STU *pb = NULL, *pf = NULL;
    pf = *p_head;
    if(*p_head == NULL) { // 1.头结点为空，直接插入
        *p_head = p_new;
        p_new->next = NULL;
        return ;
    }

    while((p_new->num >= pf->num) && (pf->next != NULL)){ // 2.遍历
        pb = pf;
        pf = pf->next;
    }

    if(p_new->num < pf->num) {// 3.找到一个pf指向的节点的num比新来的节点的num大，则插到pf节点的前面。
        if(pf == *p_head) {// 3.1.找的节点是头结点，插到对前面
            *p_head = p_new;
            p_new->next = pf;
        } else {// 3.2.找到的是中间节点，插在中间节点pf的前面
            pb->next = p_new;
            p_new->next = pf;
        }
    } else {// 4.没有找到一个节点的num比新来的节点的num大，插在末尾
        pf->next = p_new;
        p_new->next = NULL
    }
}

今天无意间翻开了数据结构，忽然扫到了双向链表，就想着重新把代码码一遍练练手。三两分钟就写完了，运行时就尴尬了。发现没有输出。
 于是我就debug了一下，就发现，每次插入的元素的pre竟然是元素本身经过调试后，发现pre为空，我意识到得重新把逻辑理一遍，于是稍作修改，测试通过：
 
//按顺序插入元素
    public void addOrder(Hero hero){
        Hero temp = head;
        boolean flag = false;
        boolean flag1 = false;
        while(true){
            if(temp.next == null){//判断插入的元素是否是最后一个元素
                flag1 = true;
                break;
            }
            if(temp.next.no == hero.no){//判断元素是否已存在
                flag = true;
                break;
            }else if(hero.no<temp.next.no){
                break;
            }
            temp = temp.next;
        }
        if(flag){
            System.out.println("元素已存在");
        }else if(flag1){
            //在temp后面插入
            hero.next = temp.next;
            temp.next = hero;
            hero.pre = temp;
            flag1 = false;
        }else{//在temp后面插入
                hero.next = temp.next;
                temp.next.pre = hero;
                temp.next = hero;
                hero.pre = temp;
        }
    }
 
欢迎各位大佬继续指正。