`

（转）单链表18个操作

 
阅读更多
#include "stdafx.h"
#include "stdio.h"
#include <stdlib.h>
#include "string.h"
 
typedef int elemType ;
 
/************************************************************************/
/*             以下是关于线性表链接存储（单链表）操作的18种算法        */
 
/* 1.初始化线性表，即置单链表的表头指针为空 */
/* 2.创建线性表，此函数输入负数终止读取数据*/
/* 3.打印链表，链表的遍历*/
/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
/* 5.返回单链表的长度 */
/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
/* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
/* 10.向单链表的表头插入一个元素 */
/* 11.向单链表的末尾添加一个元素 */
/* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
/* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
/* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
/* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
/* 18.交换2个元素的位置 */
/* 19.将线性表进行快速排序 */
 
 
/************************************************************************/
typedef struct Node{    /* 定义单链表结点类型 */
    elemType element;
    Node *next;
}Node;
 
 
/* 1.初始化线性表，即置单链表的表头指针为空 */
void initList(Node **pNode)
{
    *pNode = NULL;
    printf("initList函数执行，初始化成功\n");
}
 
/* 2.创建线性表，此函数输入负数终止读取数据*/
Node *creatList(Node *pHead)
{
    Node *p1;
    Node *p2;
 
    p1=p2=(Node *)malloc(sizeof(Node)); //申请新节点
    if(p1 == NULL || p2 ==NULL)
    {
        printf("内存分配失败\n");
        exit(0);
    }
    memset(p1,0,sizeof(Node));
 
    scanf("%d",&p1->element);    //输入新节点
    p1->next = NULL;         //新节点的指针置为空
    while(p1->element > 0)        //输入的值大于0则继续，直到输入的值为负
    {
        if(pHead == NULL)       //空表，接入表头
        {
            pHead = p1;
        }
        else               
        {
            p2->next = p1;       //非空表，接入表尾
        }
        p2 = p1;
        p1=(Node *)malloc(sizeof(Node));    //再重申请一个节点
        if(p1 == NULL || p2 ==NULL)
        {
        printf("内存分配失败\n");
        exit(0);
        }
        memset(p1,0,sizeof(Node));
        scanf("%d",&p1->element);
        p1->next = NULL;
    }
    printf("creatList函数执行，链表创建成功\n");
    return pHead;           //返回链表的头指针
}
 
/* 3.打印链表，链表的遍历*/
void printList(Node *pHead)
{
    if(NULL == pHead)   //链表为空
    {
        printf("PrintList函数执行，链表为空\n");
    }
    else
    {
        while(NULL != pHead)
        {
            printf("%d ",pHead->element);
            pHead = pHead->next;
        }
        printf("\n");
    }
}
 
/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
void clearList(Node *pHead)
{
    Node *pNext;            //定义一个与pHead相邻节点
 
    if(pHead == NULL)
    {
        printf("clearList函数执行，链表为空\n");
        return;
    }
    while(pHead->next != NULL)
    {
        pNext = pHead->next;//保存下一结点的指针
        free(pHead);
        pHead = pNext;      //表头下移
    }
    printf("clearList函数执行，链表已经清除\n");
}
 
/* 5.返回单链表的长度 */
int sizeList(Node *pHead)
{
    int size = 0;
 
    while(pHead != NULL)
    {
        size++;         //遍历链表size大小比链表的实际长度小1
        pHead = pHead->next;
    }
    printf("sizeList函数执行，链表长度 %d \n",size);
    return size;    //链表的实际长度
}
 
/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
int isEmptyList(Node *pHead)
{
    if(pHead == NULL)
    {
        printf("isEmptyList函数执行，链表为空\n");
        return 1;
    }
    printf("isEmptyList函数执行，链表非空\n");
 
    return 0;
}
 
/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
elemType getElement(Node *pHead, int pos)
{
    int i=0;
 
    if(pos < 1)
    {
        printf("getElement函数执行，pos值非法\n");
        return 0;
    }
    if(pHead == NULL)
    {
        printf("getElement函数执行，链表为空\n");
        return 0;
        //exit(1);
    }
    while(pHead !=NULL)
    {
        ++i;
        if(i == pos)
        {
            break;
        }
        pHead = pHead->next; //移到下一结点
    }
    if(i < pos)                  //链表长度不足则退出
    {
        printf("getElement函数执行，pos值超出链表长度\n");
        return 0;
    }
 
    return pHead->element;
}
 
/* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
elemType *getElemAddr(Node *pHead, elemType x)
{
    if(NULL == pHead)
    {
        printf("getElemAddr函数执行，链表为空\n");
        return NULL;
    }
    if(x < 0)
    {
        printf("getElemAddr函数执行，给定值X不合法\n");
        return NULL;
    }
    while((pHead->element != x) && (NULL != pHead->next)) //判断是否到链表末尾，以及是否存在所要找的元素
    {
        pHead = pHead->next;
    }
    if((pHead->element != x) && (pHead != NULL))
    {
        printf("getElemAddr函数执行，在链表中未找到x值\n");
        return NULL;
    }
    if(pHead->element == x)
    {
        printf("getElemAddr函数执行，元素 %d 的地址为 0x%x\n",x,&(pHead->element));
    }
 
    return &(pHead->element);//返回元素的地址
}
 
/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
int modifyElem(Node *pNode,int pos,elemType x)
{
    Node *pHead;
    pHead = pNode;
    int i = 0;
 
    if(NULL == pHead)
    {
        printf("modifyElem函数执行，链表为空\n");
    }
    if(pos < 1)
    {
        printf("modifyElem函数执行，pos值非法\n");
        return 0;
    }
    while(pHead !=NULL)
    {
        ++i;
        if(i == pos)
        {
            break;
        }
        pHead = pHead->next; //移到下一结点
    }
    if(i < pos)                  //链表长度不足则退出
    {
        printf("modifyElem函数执行，pos值超出链表长度\n");
        return 0;
    }
    pNode = pHead;
    pNode->element = x;
    printf("modifyElem函数执行\n");
     
    return 1;
}
 
/* 10.向单链表的表头插入一个元素 */
int insertHeadList(Node **pNode,elemType insertElem)
{
    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));
    memset(pInsert,0,sizeof(Node));
    pInsert->element = insertElem;
    pInsert->next = *pNode;
    *pNode = pInsert;
    printf("insertHeadList函数执行，向表头插入元素成功\n");
 
    return 1;
}
 
/* 11.向单链表的末尾添加一个元素 */
int insertLastList(Node **pNode,elemType insertElem)
{
    Node *pInsert;
    Node *pHead;
    Node *pTmp; //定义一个临时链表用来存放第一个节点
 
    pHead = *pNode;
    pTmp = pHead;
    pInsert = (Node *)malloc(sizeof(Node)); //申请一个新节点
    memset(pInsert,0,sizeof(Node));
    pInsert->element = insertElem;
 
    while(pHead->next != NULL)
    {
        pHead = pHead->next;
    }
    pHead->next = pInsert;   //将链表末尾节点的下一结点指向新添加的节点
    *pNode = pTmp;
    printf("insertLastList函数执行，向表尾插入元素成功\n");
 
    return 1;
}
 
/* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
 
 
/* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
/* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
/* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
/* 18.交换2个元素的位置 */
/* 19.将线性表进行快速排序 */
 
/******************************************************************/
int main()
{
    Node *pList=NULL;
    int length = 0;
 
    elemType posElem;
 
    initList(&pList);       //链表初始化
    printList(pList);       //遍历链表，打印链表
 
    pList=creatList(pList); //创建链表
    printList(pList);
     
    sizeList(pList);        //链表的长度
    printList(pList);
 
    isEmptyList(pList);     //判断链表是否为空链表
     
    posElem = getElement(pList,3);  //获取第三个元素，如果元素不足3个，则返回0
    printf("getElement函数执行，位置 3 中的元素为 %d\n",posElem);  
    printList(pList);
 
    getElemAddr(pList,5);   //获得元素5的地址
 
    modifyElem(pList,4,1);  //将链表中位置4上的元素修改为1
    printList(pList);
 
    insertHeadList(&pList,5);   //表头插入元素12
    printList(pList);
 
    insertLastList(&pList,10);  //表尾插入元素10
    printList(pList);
 
    clearList(pList);       //清空链表
    system("pause");
     
}

　　本文来自：http://www.cnblogs.com/lifuqing/archive/2011/08/20/List.html

分享到：
| （转）合并两个有序线性表的元素(C语言版)
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    数据结构-填空题.doc

    6. 链栈的出栈操作：将栈顶元素的值保存，并更新栈顶指针，指向下一个元素。 7. 单向链表转换成循环链表：将末尾节点的指针指向头节点。 8. 循环队列的满条件：队头指针和队尾指针经过加1运算后相等，表示队列已满...

    数据结构实验二-栈的转换

    3. **掌握数制转换算法**：学会利用栈来实现从十进制到其他任意进制（如二进制、八进制等）的转换。 #### 实验要求 1. **理论准备**：仔细研读相关的理论知识和算法描述，确保对栈的基本操作有充分的理解。 2. **...

    计算机数据结构实验指导.pdf

    "计算机数据结构实验指导" ...实验内容包括：利用栈结构，编写程序将十进制数转换成二进制数或八进制数。 知识点： * 堆栈的存储方式和基本操作 * 堆栈后进先出运算原则 * 堆栈在解决实际问题中的应用

    (完整)《C语言程序设计课程设计》题目-软件工程2班.docx

    "C语言程序设计课程设计" 根据给定的文件信息，我们可以生成以下相关知识点： ...* 十进制整数的转换：需要实现十进制整数N向其它进制数d（二、八、十六）的转换，转换法则是根据计算机实现计算的基本问题。

    自己写的C语言的一些简单程序~（包括简单链表等）

    在提供的代码中，我们看到几个关于链表操作的实例，包括单链表和循环链表的创建、插入、遍历、计数、倒序输出、检索、复制和打印。下面将详细解释这些知识点： 1. **链表头**： 链表头是链表的起始节点，通常包含...

    考研备考资料真题-2017年苏州大学数据结构与操作系统考研试题真题.docx

    分页机制是现代操作系统中普遍采用的一种内存管理技术，它将进程的逻辑地址空间划分为大小固定的页面，每个页面映射到物理内存的一个或多个物理块上。题目中给出了一个进程p的页表，通过分析页表可以将逻辑地址转换...

    数据结构——堆栈和队列

    十进制转八进制的转换是数字系统转换的一个实例。在计算机科学中，我们经常需要在不同的进制之间进行转换。这个转换可以通过长除法实现，将十进制数除以8，然后收集余数，逆序排列余数就得到了八进制数。在这个实现...

    C C++算法实例.c

    设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负 进制下的数：-R∈{-2，-3，-4,....-20} 八 全排列与组合的生成 1.排列的生成：（1..n） 2.组合的生成(1..n中选取k个数的...

    C语言程序设计课程设计题目.docx

    4. 数制转换：例如，将十进制整数转换为二进制、八进制或十六进制，可以利用栈的性质，将整数不断除以目标基数，将余数压栈，最后从栈中读取余数逆序即为目标进制的数字。 这些课程设计题目涵盖了C语言的基础知识、...

    《数据结构实验》讲义.docx

    在实验中，学生需要实现非负十进制整数到八进制整数的转换，这通常通过辗转相除法实现。此外，还需编写程序检查算术表达式的括号是否正确配对，这涉及到深度优先搜索（DFS）或栈的特性来判断括号平衡。 总的来说，...

    12计应复习卷

    - 第八题给出了深度为6的二叉树至多可能拥有的结点数为63个。这可以通过公式\(2^k - 1\)来计算，其中\(k\)表示二叉树的深度。 9. **树到二叉树的转换**： - 第九题提到树转换为二叉树后形态是唯一的。这种转换...

    数据结构课程部分代码（适于初学者）

    在这个文件中，栈被用来实现数字的基数转换，例如将十进制数转换为二进制、八进制或十六进制。 3. **二叉树.cpp**：二叉树是一种每个节点最多有两个子节点的数据结构。代码可能包括了二叉树的基本操作，如前序、...

    第1235章课堂练习1

    6. **链表的删除操作**：对于带尾指针的单链表，删除最后一个节点是O(1)的复杂度，因为可以直接通过尾指针找到并删除；删除第一个节点是O(n)的复杂度，因为需要遍历到尾部更新尾指针。 7. **顺序表的反转**：长度为...

    数据结构期末复习资料111

    14. **队列操作**：在不带头结点的单链表队列中，删除操作可能涉及调整队头和队尾指针。 15. **哈夫曼树**：哈夫曼树的特点是权值大的叶子离根节点近，无度为1的内部节点，以及N棵树合并得到的哈夫曼树有2N-1个节点...

    数据结构试题 练手的好例子

    15. 链表操作：第18题展示了在链表中插入节点的正确操作。 16. 单链表操作：第19题继续讨论链表操作，涉及删除节点。 这些题目覆盖了数据结构的基础知识，通过解决这些问题，可以深入理解各种数据结构的特性和操作...

    江西财经大学《计算机基础》三套期末考试试卷（含答案）.pdf

    16. 链表操作：单链表的节点插入操作需要正确处理指针。问题16考察的是数据结构中链表操作的知识。 17. 二叉树知识：在二叉树中，叶子节点的个数与树的深度有关。问题17考察的是二叉树的结构特性。 18. 特定条件下...

Magicbox
Global site tag (gtag.js) - Google Analytics