c语言程序链表问题

*** 作系统 win 8.1//编译环境 Visual Stuido 2017#include#include#includetypedef int ElementType //定义数据类型,可根据需要进行其他类型定义//链表节点的定义typedef struct ListNode {

ElementType Element //数据域，存放数据

ListNode* Next //指向下一个链表节点}Node, *PNode//链表创建函数定义PNode CreateList(void) {int len//用于定义链表长度

int val//用于存放节点数值

PNode PHead = (PNode)malloc(sizeof(Node)) //创建分配一个头节点内存空间

//头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）

if (PHead == NULL)//判断是否分配成功{

printf("空间分配失败 \n")

exit(-1)

}

PNode PTail = PHead //链表的末尾节点，初始指向头节点

PTail->Next = NULL //最后一个节点指针置为空

printf("请输入节点个数：")

scanf_s("%d", &len) //输入节点个数

for (int i = 0i <leni++) {

PNode pNew = (PNode)malloc(sizeof(Node)) //分配一个新节点

if (pNew == NULL) {

printf("分配新节点失败\n")

exit(-1)

}

printf("请输入第 %d 个节点的数据：", i + 1)

scanf_s("%d", &val) //输入链表节点的数据

pNew->Element = val //把数据赋值给节点数据域

PTail->Next = pNew //末尾节点指针指向下一个新节点

pNew->Next = NULL //新节点指针指向为空

PTail = pNew //将新节点复制给末尾节点}

printf("创建链表成功\n") return PHead //返回头节点}//主函数 int main() {

PNode List = CreateList() //创建一个指针，使其指向新创建的链表的头指针

return 0

}

链表在程序执行过程中是可以变化的。

以单向链表的增加长度的实现为例：

链表是一个个节点组成的，节点是由节点的内容和下一个节点的地址组成，而且每一个节点都持有这下一个节点的内存地址，

所以在在程序的执行过程中，只需要重新创建一个新节点，然后将当前链表的尾节点持有新生成的节点的地址，这个时候链表的长度就新增一了。所以链表在程序执行期间长度是可变的。

与链表对应的是数组，它们是数据的两种存储方式，数组的大小是在编译器就确定了所需内存大小。

而链表所需的内存地址不是连续的，且可以动态增减长度。

前阵子做的用单向链表实现约瑟夫问题：

有M个人围一圈玩报数，凡报到N的出退出，输出每次退出的人的编号。

#include

"stdio.h"

struct

game

{

int

ID

game

*pNext

}

void

main()

{

int

i,m=17,n=3

game

*pPrev,*pNode,*pTop

printf("Input

M

N:")

scanf("%d

%d",&m,&n)

if(n>m||n<1)

return

pTop=new

game

pTop->ID=1

pPrev=pTop

for(i=2i<=mi++)

{

pNode=new

game

pNode->ID=i

pPrev->pNext=pNode

pPrev=pNode

}

pNode->pNext=pTop

pPrev=pNode

pNode=pTop

i=0

while(pNode->pNext!=pNode)

{

i++

if(i%n==0)

{

printf("%d

",pNode->ID)

pPrev->pNext=pNode->pNext

delete

pNode

pNode=pPrev->pNext

i=0

}

else

{

pPrev=pNode

pNode=pNode->pNext

}

}

delete

pNode

}

---