#include\x0d\x0a#include\x0d\x0a#include \x0d\x0a//先定义一种student类型,表示一个学生的信息，如下：\x0d\x0atypedef struct student\x0d\x0a{\x0d\x0aint num//表示
学号\x0d\x0achar name[30]//表示姓名\x0d\x0afloat score//表示分数\x0d\x0a}student\x0d\x0a//定义一种NODE类型,表示一个
结点信息，如下：\x0d\x0atypedef struct node\x0d\x0a{\x0d\x0astudent st//表示一个学生的信息\x0d\x0astruct node *next//表示一个NODE类型的指针\x0d\x0a}NODE\x0d\x0a//1、写出建立一个带头结点的线性链表的函数，其中每个结点包括学号、姓名、分数三个数据域。函数形式如下：\x0d\x0aNODE *creat_link(int direction)\x0d\x0a{\x0d\x0aNODE *head,*p,*tail\x0d\x0aint xh,i=1\x0d\x0aif(direction==1) //当direction的值为1时，新建立的结点连到尾部\x0d\x0a{\x0d\x0atail=head=(NODE *)malloc(sizeof(NODE))\x0d\x0ahead->next=NULL\x0d\x0aprintf("请输入第%d个学生的学号：",i)\x0d\x0ascanf("%d",&xh)\x0d\x0awhile(xh>0) //从键盘临时输入学生情况，当输入的学号非正，则链表建立完毕\x0d\x0a{\x0d\x0ap=(NODE *)malloc(sizeof(NODE))\x0d\x0ap->st.num=xh\x0d\x0aprintf("请输入第%d个学生的姓名：",i)\x0d\x0ascanf("%s",p->st.name)\x0d\x0aprintf("请输入第%d个学生的成绩：",i)\x0d\x0ascanf("%f",&p->st.score)\x0d\x0ap->next=NULL\x0d\x0atail->next=p\x0d\x0atail=p\x0d\x0ai=i+1\x0d\x0aprintf("请输入第%d个学生的学号：",i)\x0d\x0ascanf("%d",&xh)\x0d\x0a}\x0d\x0a}\x0d\x0aelse if(direction==0) //当direction为0时，新建立的结点成为第一个结点\x0d\x0a{\x0d\x0ahead=(NODE *)malloc(sizeof(NODE))\x0d\x0ahead->next=NULL\x0d\x0aprintf("请输入第%d个学生的学号：",i)\x0d\x0ascanf("%d",&xh)\x0d\x0awhile(xh>0) //从键盘临时输入学生情况，当输入的学号非正，则链表建立完毕\x0d\x0a{\x0d\x0ap=(NODE *)malloc(sizeof(NODE))\x0d\x0ap->st.num=xh\x0d\x0aprintf("请输入第%d个学生的姓名：",i)\x0d\x0ascanf("%s",p->st.name)\x0d\x0aprintf("请输入第%d个学生的成绩：",i)\x0d\x0ascanf("%f",&p->st.score)\x0d\x0ap->next=head->next\x0d\x0ahead->next=p\x0d\x0ai=i+1\x0d\x0aprintf("请输入第%d个学生的学号：",i)\x0d\x0ascanf("%d",&xh)\x0d\x0a}\x0d\x0a}\x0d\x0areturn head\x0d\x0a}\x0d\x0a//2、写出输出上述链表各结点数据域值的函数。该函数对应的函数需要一个形参，表示链表的头指针，形式如下：\x0d\x0avoid print_link(NODE *head)\x0d\x0a{\x0d\x0aNODE *p\x0d\x0ap=head->next\x0d\x0aprintf("%-10s%-20s%-10s\n","学号","姓名","分数")\x0d\x0awhile(p!=NULL)\x0d\x0a{\x0d\x0aprintf("%-10d%-20s%-10.1f\n",p->st.num,p->st.name,p->st.score)\x0d\x0ap=p->next\x0d\x0a}\x0d\x0a//该函数能输出head所指的链表的所有结点值，输出形式如下：\x0d\x0a/*本函数输出线性表sq中所有数据，形式如下：\x0d\x0a学号 姓名 分数\x0d\x0a12 张三 234.5\x0d\x0a18 李四 987.7\x0d\x0a??? ??? ??.*/\x0d\x0a}\x0d\x0a//3、写出在链表中删除结点的函数\x0d\x0aint del_link(NODE *head,char name[])\x0d\x0a{\x0d\x0aNODE *p,*p1\x0d\x0ap=head->next\x0d\x0ap1=head\x0d\x0awhile(p!=NULL)\x0d\x0a{\x0d\x0aif(strcmp(p->st.name,name)!=0)\x0d\x0a{\x0d\x0ap1=p\x0d\x0ap=p->next\x0d\x0a}\x0d\x0aelse\x0d\x0a{\x0d\x0abreak\x0d\x0a}\x0d\x0a}\x0d\x0aif(p!=NULL)\x0d\x0a{\x0d\x0ap1->next=p->next\x0d\x0afree(p)\x0d\x0areturn 1\x0d\x0a}\x0d\x0aelse\x0d\x0a{\x0d\x0areturn 0\x0d\x0a}\x0d\x0a//删除head所指的链表中，名字为name的结点，删除成功返回1，不成功返回0\x0d\x0a}\x0d\x0a//4、写出在链表中
插入结点的算法\x0d\x0aint insert(NODE *head,student x,int wz)\x0d\x0a{\x0d\x0aNODE *p=head\x0d\x0aint i=0,jg\x0d\x0aif(wznext\x0d\x0a}\x0d\x0aif(p==NULL)\x0d\x0a{\x0d\x0ajg=0\x0d\x0a}\x0d\x0aif(i=wz-1)\x0d\x0a{\x0d\x0a//找到wz前面的节点，p指向它\x0d\x0aNODE *q\x0d\x0aq=(NODE *)malloc(sizeof(NODE))\x0d\x0aq->st.num=x.num\x0d\x0astrcpy(q->st.name,x.name)\x0d\x0aq->st.score=x.score\x0d\x0aq->next=p->next\x0d\x0ap->next=q\x0d\x0ajg=1\x0d\x0a}\x0d\x0a}\x0d\x0areturn jg\x0d\x0a//该函数能够在wz这个结点之前，插入一个新结点，新结点的数据域为x。插入成功返回1，不成功返回0。\x0d\x0a}\x0d\x0a//5、写出主函数，分别调用上面算法所对应的程序，建立链表，并输出链表的值。\x0d\x0avoid main()\x0d\x0a{\x0d\x0aNODE *head//定义指针变量head\x0d\x0aint wz//表示插入位置\x0d\x0achar xm[30]\x0d\x0astudent st//定义一个变量st，用来表示一个学生的信息\x0d\x0ahead=creat_link(1)\x0d\x0aprint_link(head)//调用函数建立链表，并把返回值送给head\x0d\x0a//调用函数，输出链表中各个结点的值\x0d\x0a//输入一个学生的有关信息，送给变量st的有关成员\x0d\x0aprintf("\n\n请输入要插入的位置：")\x0d\x0ascanf("%d",&wz)//输入wz的值\x0d\x0aprintf("请输入要插入的学生的学号：")\x0d\x0ascanf("%d",&st.num)\x0d\x0aprintf("请输入要插入的学生的姓名：")\x0d\x0ascanf("%s",st.name)\x0d\x0aprintf("请输入要插入的学生的成绩：")\x0d\x0ascanf("%f",&st.score)\x0d\x0a//调用函数，在链表中把学生st的值作为一个结点插入,如果插入成功，输出新链表\x0d\x0aif(insert(head,st,wz)==1)\x0d\x0a{\x0d\x0aprintf("\n插入成功，新表为：\n")\x0d\x0aprint_link(head)\x0d\x0a}\x0d\x0aelse\x0d\x0a{\x0d\x0aprintf("插入不成功")\x0d\x0a}\x0d\x0a//调用函数，在链表中删除一个指定结点的值,如果删除成功，输出新链表\x0d\x0aprintf("\n\n请输入要删除的学生的姓名：")\x0d\x0agetchar()\x0d\x0agets(xm)\x0d\x0aif(del_link(head,xm)==1)\x0d\x0a{\x0d\x0aprintf("\n删除成功，新表为：\n")\x0d\x0aprint_link(head)\x0d\x0a}\x0d\x0aelse\x0d\x0a{\x0d\x0aprintf("删除不成功")\x0d\x0a}\x0d\x0a}import java.io.*
public class List {
// 用变量来实现表头
private Node Head = null
private Node Tail = null
private Node Pointer = null
private int Length = 0
/** 清空整个链表 */
public void deleteAll() {
Head = null
Tail = null
Pointer = null
Length = 0
}
/** 链表复位，使第一个结点 成为当前结点 */
public void reset() {
Pointer = null
}
/** 判断链表是否为空 */
public boolean isEmpty() {
return (Length == 0)
}
/** 判断当前结点是否 为最后一个结点 */
public boolean isEnd() {
if (Length == 0)
throw new java.lang.NullPointerException()
else if (Length == 1)
return true
else
return (cursor() == Tail)
}
/** 返回当前结点的下一个结点的值， 并使其成为当前结点 */
public Object nextNode() {
if (Length == 1)
throw new java.util.NoSuchElementException()
else if (Length == 0)
throw new java.lang.NullPointerException()
else {
Node temp = cursor()
Pointer = temp
if (temp != Tail)
return (temp.next.data)
else
throw new java.util.NoSuchElementException()
}
}
/** 返回当前结点的值 */
public Object currentNode() {
Node temp = cursor()
return temp.data
}
/** 在当前结点前插入一个结点， 并使其成为当前结点 */
public void insert(Object d) {
Node e = new Node(d)
if (Length == 0) {
Tail = e
Head = e
} else {
Node temp = cursor()
e.next = temp
if (Pointer == null)
Head = e
else
Pointer.next = e
}
Length++
}
/** 返回链表的大小 */
public int size() {
return (Length)
}
/**
* 将当前结点移出链表，下一个结点成为当前结点， 如果移出的结点是最后一个结点，则第一个结点成为当前结点
*/
public Object remove() {
Object temp
if (Length == 0)
throw new java.util.NoSuchElementException()
else if (Length == 1) {
temp = Head.data
deleteAll()
} else {
Node cur = cursor()
temp = cur.data
if (cur == Head)
Head = cur.next
else if (cur == Tail) {
Pointer.next = null
Tail = Pointer
reset()
} else
Pointer.next = cur.next
Length--
}
return temp
}
/** 返回当前结点的指针 */
private Node cursor() {
if (Head == null)
throw new java.lang.NullPointerException()
else if (Pointer == null)
return Head
else
return Pointer.next
}
/** 链表的简单应用举例 */
public static void main(String[] args) {
List a = new List()
for (int i = 1i <= 10i++)
a.insert(new Integer(i))
System.out.println(a.currentNode())
while (!a.isEnd())
System.out.println(a.nextNode())
a.reset()
while (!a.isEnd()) {
a.remove()
}
a.remove()
a.reset()
if (a.isEmpty())
System.out.println("There is no Node in List \n")
System.out.println("You can press return to quit\n")
try {
// 确保用户看清程序运行结果
System.in.read()
} catch (IOException e) {
}
}
}
// 构成链表的结点定义
class Node {
Object data
Node next
Node(Object d) {
data = d
next = null
}
}
建立一个单链表，实现插入与删除功能的代码如下：
///单链表
#include<iostream>
using namespace std
typedef int elemtype //数据类型模版
struct Lnode //结点
{
elemtype data
Lnode *next
}
///建表
void creat_Link(Lnode &head)
{
Lnode *p,*q
int n
p=new Lnode
head=p
cout<<"输入链表长度:"<<endl
cin>>n
cout<<"输入数据:"<<endl
cin>>p->data
q=p
for(int i=1i<=n-1i++)
{
p=new Lnode
//cout<<"输入数据:"
cin>>p->data
q->next=p
q=p
}
q->next=NULL
}
///表的输出
void output_Link(Lnode *&head)
{
if(head==NULL)
{cout<<"空链表!"<<endl
return}
Lnode *q
q=head
//cout<<"此链表为:"
while(q!=NULL)
{
cout<<q->data<<" "
q=q->next
}
cout<<endl
}
///表的插入
void insert_Link(Lnode *&head)
{
int i
cout<<"输入要插入的位置:"
cin>>i
Lnode *q,*iq
q=head
for(int j=1j<ij++)
{
iq=q
q=q->next
}
cout<<"输入插入的数据:"
Lnode *p
p=new Lnode
cin>>p->data
p->next=iq->next
iq->next=p
cout<<endl
}
///表的数据删除
void Delete_Link(Lnode *&head)
{
cout<<"输入删除的位置:"
int i
cin>>i
if(i==1)
head=head->next
else
{
Lnode *p,*q
q=head
for(int j=1j<ij++)
{p=q
q=q->next
}
p->next=q->next
delete q
cout<<endl
}
}
int main()
{
Lnode *head
head=NULL
creat_Link(head)
insert_Link(head)
output_Link(head)
Delete_Link(head)
output_Link(head)
return 0
}
[扩展]
以“结点的序列”表示线性表称作线性链表（单链表），链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
微信扫一扫
支付宝扫一扫
评论列表（0条）