Question

单链表问题用C语言编写

已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前

Answer 1

用一组地址任意的存储单元存放线性表中的数据元素。
　　以元素(数据元素的映象)
　　+ 指针(指示后继元素存储位置)
　　= 结点
　　(表示数据元素 或 数据元素的映象)
　　以“结点的序列”表示线性表
　　�8�7�8�7 称作线性链表（单链表）
　　单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。
　　因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i
　　单链表
　　1、链接存储方法
　　链接方式存储的线性表简称为链表（Linked List）。
　　链表的具体存储表示为：
　　① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
　　② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
　　注意：
　　链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。
　　2、链表的结点结构
　　┌──┬──┐
　　│data│next│
　　└──┴──┘
　　data域--存放结点值的数据域
　　next域--存放结点的直接后继的地址（位置）的指针域（链域）
　　注意：
　　①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
　　②每个结点只有一个链域的链表称为单链表（Single Linked List）。
　　【例】线性表（bat，cat，eat，fat，hat，jat，lat，mat）的单链表示如示意图
　　3、头指针head和终端结点指针域的表示
　　单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。
　　注意：
　　链表由头指针唯一确定，单链表可以用头指针的名字来命名。
　　【例】头指针名是head的链表可称为表head。
　　终端结点无后继，故终端结点的指针域为空，即NULL。
　　4、单链表的一般图示法
　　由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（bat，cat，fat，hat，jat，lat，mat）的单链表就可以表示为下图形式。
　　5、单链表类型描述
　　typedef char DataType; //假设结点的数据域类型为字符
　　typedef struct node{ //结点类型定义
　　DataType data; //结点的数据域
　　struct node *next;//结点的指针域
　　}ListNode;
　　typedef ListNode *LinkList;
　　ListNode *p;
　　LinkList head;
　　注意：
　　①LinkList和ListNode *是不同名字的同一个指针类型（命名的不同是为了概念上更明确）
　　②LinkList类型的指针变量head表示它是单链表的头指针
　　③ListNode *类型的指针变量p表示它是指向某一结点的指针
　　6、指针变量和结点变量
　　┌────┬────────────┬─────────────┐
　　│　│　指针变量　│　结点变量 │
　　├────┼────────────┼─────────────┤
　　│ 定义 │在变量说明部分显式定义 │在程序执行时，通过标准 │
　　│ │ │函数malloc生成 │
　　├────┼────────────┼─────────────┤
　　│ 取值 │ 非空时，存放某类型结点 │实际存放结点各域内容 │
　　│ │的地址 │ │
　　├────┼────────────┼─────────────┤
　　│操作方式│ 通过指针变量名访问 │ 通过指针生成、访问和释放 │
　　└────┴────────────┴─────────────┘
　　①生成结点变量的标准函数
　　p=( ListNode *)malloc(sizeof(ListNode))；
　　//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中
　　②释放结点变量空间的标准函数
　　free(p)；//释放p所指的结点变量空间
　　③结点分量的访问
　　利用结点变量的名字*p访问结点分量
　　方法一：(*p).data和(*p).next
　　方法二：p-﹥data和p-﹥next
　　④指针变量p和结点变量*p的关系
　　指针变量p的值——结点地址
　　结点变量*p的值——结点内容
　　(*p).data的值——p指针所指结点的data域的值
　　(*p).next的值——*p后继结点的地址
　　*((*p).next)——*p后继结点
　　注意：
　　① 若指针变量p的值为空（NULL），则它不指向任何结点。此时，若通过*p来访问结点就意味着访问一个不存在的变量，从而引起程序的错误。
　　② 有关指针类型的意义和说明方式的详细解释
　　可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。
　　因此，在单链表中第 i 个结点之前进行插入的基本操作为:
　　找到线性表中第i-1个结点，然后修改其指向后继的指针。
#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define Status inttypedef int ElemType;/*此处利用#define或typedef 将ElemType先作定义*//*此处需补充定义链表的结构类型声明*/LinkList InitList(){LinkList head;</p><p>head=(LinkList)malloc(sizeof(LNode));</p><p>head->next=NULL;</p><p>return head;}void printlist(LinkList L) //这是一个输出表元的函数{LinkList p;</p><p>p=L->next;</p><p>while(p!=NULL)</p><p>{补充一条语句；</p><p>补充一条语句；}}void CreateListF(LinkList &L , int n ) // 单号的同学用头插法建表{ /* 补充N条语句，实现用值来建表 */ } void CreateListR(LinkList &L , int n ) // 双号的同学用尾插法建表{ /* 补充N条语句，实现用值来建表 */ } /*补充一个算法函数，查找表中值为X元素 */void main(){LinkList y;</p><p>int n;</p><p>printf("请输入N的值，它代表y中元素个数：");</p><p>scanf("%d",&n);</p><p>printf("\n");</p><p>/*此处调用上面的建表函数*/</p><p>printf("\n");</p><p>printf("这是链表y中的元素：");</p><p>/*此处调用上面的函数输出y表中的元素 */</p><p>printf("\n\n\n");</p><p></p><p>/*此处要补充语句，调用上面的查找表元素的函数*/</p><p></p><p>printf("\n\n\n");</p><p></p><p></p><p>}

Answer 2

LinkedList DelInsert ( LinkedList &heada, LinkedList &headb, int i, int j, int len )
//heada和headb均是带头结点的单链表。本算法删除heada链表中自第i个元素起的共len个元素, 然后将单链表heada插入到headb的第j个元素之前。
{
if ( i < 1 || len < 1 || j < 1)
{
printf ( "参数错误\n");
exit ( 0);
}
p = heada; //p为链表A的工作指针, 初始化为A的头指针, 查到第i个元素时, p指向第i-1个元素
int k = 0; //计数
while ( p != null && k < i-1) //查找第i个结点。
{
k++;
p = p->next;
}
if ( p == null) //i太大, 退出算法
{
printf ( "给的%d太大了\n", i);
exit ( 0);
}
q = p->next; //q为工作指针, 初始指向A链表第一个被删结点。
k = 0;
while ( q != null && k < len)
{
k++;
u = q;
q = q->next;
free ( u); //删除结点, 后移指针。
}
if ( k < len)
{
printf ( "给的%d太大了\n", len);
exit ( 0);
}
p->next=q; //A链表删除了len个元素。
if ( heada->next!=null) //heada->next=null说明链表中结点均已删除, 无需往B表插入
{
while ( p->next != null) //找A的尾结点。
p = p->next;
q = headb; //q为链表B的工作指针。
k = 0; //计数
while ( q != null && k < j - 1) //查找第j个结点,查找成功时,q指向第j-1个结点
{
k++;
q = q->next;
}
if ( q == null)
{
printf ( "给的%d太大了\n", j);
exit ( 0);
}
p->next = q->next; //将A链表链入
q->next = heada->next; //A的第一元素结点链在B的第j-1个结点之后
}
free ( heada); //释放A表头结点。
return headb;
}

Answer 3

因为不知道具体问题，只能写出算法思想提供参考，假设单链表节点类型为nodenode *p,*q,*a；p=heada.next；（A的第一个元素）int k；for(k=0;k<i-1;k++)p=p.next (找出第i-1个元素）for(k=0;k<len;k++)p.next=p.next.next (删除自第i个元素起len个元素）p=headb.next (B的第一个元素）for(k=0;k<j-1;k++)p=p.next （找出B的第j-1个元素）q=p.next (q指向第j个元素)a=heada.next while(a.next!=null)a=a.next (找出A的最后一个元素）p.next=heada.next;a.next=q; (链接完成）

Answer 4

#include"stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
ElemType elem;
struct LNode *next;
}LNode,*LinkList;
Status ListInit(LinkList *L)
{
*L=(LinkList)malloc(sizeof(LNode));
if(!*L)exit(OVERFLOW);
(*L)->next=NULL;
return OK;
}
void vist(ElemType e)
{
printf("->%d",e);
}
Status ListInsert(LinkList L,int i,ElemType e)
{
int j=0;
LinkList p=L,s;
while(p&&j<i-1)
{
++j;
p=p->next;
}
if(!p||j>i-1)return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s->elem=e;
s->next=p->next;
p->next=s;
return OK;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{
LinkList p=L->next;
while(p)
{
vi(p->elem);
p=p->next;
}
}
Status Delete(LinkList L,int i,int len)
{
LinkList p,q;
int j=0;
p=L;
while(p&&j<i-1)
{
++j;
p=p->next;
}
if(!p||j>i-1)
{
printf("起始位置不合适\n");
return ERROR;
}
j=0;
q=L;
while(q&&j<i+len-1)
{
++j;
q=q->next;
}
if(!q||j>i+len-1)
{
printf("末尾位置不合适\n");
return ERROR;
}
p->next=q->next;
return OK;
}
Status Insert(LinkList LA,LinkList LB,int pos)
{
int j=0;
LinkList p=LB,q;
while(j<pos-1&&p)
{
++j;
p=p->next;
}
if(j>pos-1||!p)
{
printf("位置错误\n");
return ERROR;
}
q=LA;
while(q->next)q=q->next;
q->next=p->next;
p->next=LA->next;
return OK;
}
void main()
{
int i;
int s,t;
LinkList L,T;
ListInit(&L);
ListInit(&T);
for(i=1;i<=10;++i)
ListInsert(L,i,i);
for(i=1;i<=10;++i)
ListInsert(T,i,i);
printf("A表的元素:\n");
ListTraverse(L,vist);
printf("\n");
printf("B表的元素:\n");
ListTraverse(T,vist);
printf("\n");
Delete(L,3,1);
printf("A表删除后的元素:\n");
ListTraverse(L,vist);
printf("\n");
Insert(L,T,3);
printf("\n");
printf("A表删除后插入到B表:\n");
ListTraverse(T,vist);
}