单链表的实现

无头结点单链表

#include #include #define null 0

typedef char ElemType; typedef struct LNode {

ElemType data; struct LNode *next; }

LNode, *LinkList;

int ListLength(LinkList L);

ElemType GetElem(LinkList L,int i);

void InsertList(LinkList &L,ElemType x,int i); int DeleteElem(LinkList &L,int i); void DisplayList(LinkList L); LinkList LA; void main() {

LA=NULL; ElemType cs; int len=0;

InsertList(LA,'a',1); InsertList(LA,'B',2); InsertList(LA,'C',2); cs=GetElem(LA,3); len=ListLength(LA); DisplayList(LA); }

int ListLength(LinkList L) {

int n=0;

struct LNode *q=L; if(L==NULL) cout<<\"链表为空\"<next;

} return n; }

ElemType GetElem(LinkList L,int i) {

int j=1;

struct LNode *q=L; while(jnext; j++; }

if(q!=null) return(q->data); else cout<<\"位置参数不正确\"<int LocateElem(LinkList L,ElemType x) {

int n=0;

struct LNode *q=L;

while(q!=null&&q->data!=x) { q=q->next; n++; }

if(q==null) return(-1); else return(n+1); }

void InsertList(LinkList &L,ElemType x,int i) {

int j=1;

struct LNode *s,*q; s=new LNode; s->data=x; q=L;

if(i==1) { L=s; s->next=q; } else { while(jnext!=null) { q=q->next; j++; } if(j==i-1) { s->next=q->next; q->next=s; } else cout<<\"位置参数不正确!\"<int DeleteElem(LinkList &L,int i) {

int j=1;

struct LNode *q=L,*t; if(i==1) { t=q; L=L->next; } else { while(jnext!=null) { q=q->next; j++; } if(q->next!=null&&j==i-1) { t=q->next; q->next=t->next; } else

cout<<\"位置参数不正确!\"<void DisplayList(LinkList L) {

struct LNode *q; q=L;

cout<<\"链表元素： \"; if(q==null) cout<<\"链表为空\"<next==NULL)

cout<data<<\" \"; else {

while(q->next!=null) { cout<data<<\" \"; q=q->next; }

cout<data<<\" \"; }

cout<实验结果：

带头结点单链表

#include #include #define null 0

typedef char ElemType; typedef struct LNode {

ElemType data; struct LNode*next; }LNode, *LinkList;

int ListLength(LinkList L);

ElemType GetElem(LinkList L,int i);

void InsertList(LinkList &L,ElemType x,int i); int DeleteElem(LinkList &L,int i); void DisplayList(LinkList L); LinkList LA; void main() {

LA=(LinkList)malloc(sizeof(LNode)); LA->next=NULL; ElemType cs; int len=0;

InsertList(LA,'a',1); InsertList(LA,'B',2); InsertList(LA,'C',2); cs=GetElem(LA,3); len=ListLength(LA); DeleteElem(LA,2); DisplayList(LA); }

int ListLength(LinkList L) {

int n=0;

struct LNode *q=L->next; if(L->next==NULL) cout<<\"链表为空 \"<n++;

q=q->next; }

return n; }

ElemType GetElem(LinkList L, int i) {

int j=1;

struct LNode *q=L->next; while (jq=q->next; j++; }

if(q!=null) return (q->data); else cout<<\"位置参数不正确！\"<int LocateElem(LinkList L,ElemType x) {

int n=0;

struct LNode *q=L->next; while(q!=null&&q->data!=x) { q=q->next; n++; }

if(q==null) return (-1); else return (n+1); }

void InsertList(LinkList &L,ElemType x,int i) {

int j=1;

struct LNode *s,*q; s=new LNode; s->data=x; q=L->next; if(i==1) { L->next=s; s->next=q; } else { while (jnext!=null) { q=q->next;

j++; } if(j==i-1) { s->data=x; s->next=q->next; q->next=s; } else cout<<\"位置参数不正确！\"<int DeleteElem (LinkList &L, int i) {

int j=1;

struct LNode *q=L->next,*t; if(i==1) { t=L->next; L=L->next; } else { while (jnext==null) { q=q->next; j++; } if(q->next!=null&&j==i-1) {

t=q->next; q->next=t->next; } else cout<<\"位置参数不正确！\"<void DisplayList(LinkList L) {

struct LNode *q; q=L->next;

cout<<\"链表元素：\"; if(q==null) cout<<\"链表为空\"<next==NULL) cout<data<<\" \"; else {

while (q->next!=null) { cout<data<<\" \"; q=q->next; } cout<data<<\" \"; }

cout<实验结果：

约瑟夫问题——指向最后一个节点 #include #include typedef struct node { int data;

struct node *next; } ListNode;

typedef ListNode *LinkList;

void main() {

LinkList R; int n,k;

LinkList initRing(int n,LinkList R);

LinkList DeleteDeath(int n,int k,LinkList R);

cout<<\"总人数n= ，报数上限k= \" <>n; cin>>k; cout<R=initRing(n,R);

R=DeleteDeath(n,k,R); }

LinkList initRing(int n,LinkList R) {

ListNode *p,*q; int i;

R=q=new ListNode; for (i=1;ip=new ListNode; q->data=i; q->next=p; q=q->next; }

q->data=n; q->next=R; R=p; return R; }

LinkList DeleteDeath(int n,int k,LinkList R) {

int i,j;

ListNode *p,*q; p=R;

for(i=1;i<=n;i++) {

for(j=1;j<=k-1;j++) p=p->next ; q=p->next ;

p->next=q->next ; cout<data<<\" \"; if (i%10==0) cout<cout<实验结果：

约瑟夫问题——指向第一个节点

#include #include typedef struct node { int data;

struct node *next; } ListNode;

typedef ListNode *LinkList;

void main() {

LinkList R; int n,k;

LinkList initRing(int n,LinkList R);

LinkList DeleteDeath(int n,int k,LinkList R);

cout<<\"总人数n= ，报数上限k= \" <>n; cin>>k; cout<R=initRing(n,R);

R=DeleteDeath(n,k,R); }

LinkList initRing(int n,LinkList R) {

ListNode *p,*q; int i;

q=q->next;

R=q=new ListNode; for (i=1;ip=new ListNode; q->data=i; q->next=p; q=q->next; }

q->data=n; q->next=R; R=p; return R; }

LinkList DeleteDeath(int n,int k,LinkList R) {

int i,j;

ListNode *p,*q; p=R;

for(i=1;i<=n;i++) {

for(j=1;j<=k-1;j++) p=p->next ; q=p->next ;

p->next=q->next ; cout<data<<\" \"; if (i%10==0) cout<delete q; }

cout<