1 solutions
-
0
C :
#include <stdio.h> #include <string.h> #define MAXSIZE 11 typedef char ElemType[8]; typedef struct { ElemType data; int cur; /* index of next node */ } NodeType; NodeType space[MAXSIZE]; typedef struct { int elem; /* index of head node */ int length; int listsize; } SLinkList; void InitSpace_SL(void) { int i; memset(space, 0, sizeof(space)); for (i = 0; i < MAXSIZE - 1; ++i) { space[i].cur = i + 1; } space[MAXSIZE-1].cur = 0; } int LocateElem_SL(SLinkList *S, ElemType e) { int i; i = S->elem; while (i && strcmp(space[i].data, e)) { i = space[i].cur; } return i; } int Malloc_SL(void) { int i; i = space[0].cur; if (i) { space[0].cur = space[i].cur; } return i; } void Free_SL(int k) { space[k].cur = space[0].cur; space[0].cur = k; } void InitList(SLinkList *S) { InitSpace_SL(); S->elem = Malloc_SL(); space[S->elem].cur = 0; S->length = 0; S->listsize = MAXSIZE - 2; } void ListInsert_SL(SLinkList *S, int i, ElemType e) { int j, k, count; if (i < 1 || i > S->length+1) { return; } k = Malloc_SL(); if (k) { sprintf(space[k].data, "%s", e); j = S->elem; for (count = 1; count < i; ++count) { j = space[j].cur; } space[k].cur = space[j].cur; space[j].cur = k; S->length += 1; } } void ListDelete_SL(SLinkList *S, int i) { int j, k, count; if (i < 1 || i > S->length) { return; } j = S->elem; for (count = 1; count < i; ++count) { j = space[j].cur; } k = space[j].cur; space[j].cur = space[k].cur; Free_SL(k); S->length -= 1; } void ListPrint_SL(SLinkList *S) { int i; for (i = 0; i < MAXSIZE; ++i) { printf("%-8s%2d\n", space[i].data, space[i].cur); } for (i = 0; i < 20; ++i) { printf("*"); } printf("\n"); } int main(void) { char cmd[10]; ElemType name; int i; SLinkList S; InitList(&S); while (scanf("%s", cmd) != EOF) { switch (cmd[2]) { case 's': /* insert */ scanf("%d", &i); scanf("%s", name); ListInsert_SL(&S, i, name); break; case 'l': /* delete */ scanf("%d", &i); ListDelete_SL(&S, i); break; case 'a': /* search */ scanf("%s", name); i = LocateElem_SL(&S, name); printf("%2d\n", i); for (i = 0; i < 20; ++i) { printf("*"); } printf("\n"); break; case 'o': /* show */ ListPrint_SL(&S); break; } } return 0; }C++ :
#include <stdio.h> #include <string.h> #define MAXSIZE 11 // 静态链表的长度 typedef char ElemType[8]; // 元素的类型，规定姓氏不超过7个字符 typedef struct{ ElemType data; // 节点中的数据 int cur; // 下一个节点的下标（相当于指针） }NodeType; // 节点类型 NodeType space[MAXSIZE]; // 用来存储节点的数组，相当于一般链表中的内存， // 只是那个内存是系统分配的，我们看不到 typedef struct{ int elem; // 静态链表存储空间基址（起始元素的下标） int length; // 静态链表中的元素数目 int listSize; // 静态链表当前的长度，可容纳元素数目 }SLinkList; // 静态链表类型的定义，和一般的链表类似 int LocateElem_SL(SLinkList& S, ElemType e) { // 算法2.13 // 在静态单链线性表L中查找第1个值为e的元素。 // 若找到，则返回它在L中的位序，否则返回0。 int i; i = S.elem; // i指示表中第一个结点 while (i && strcmp(space[i].data, e)) i = space[i].cur; // 在表中顺链查找 return i; } // LocateElem_SL void InitSpace_SL() { // 算法2.14 // 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针， // "0"表示空指针 memset(space, 0 ,sizeof(space)); for (int i = 0; i < MAXSIZE - 1; ++i) space[i].cur = i + 1; space[MAXSIZE - 1].cur = 0; } // InitSpace_SL int Malloc_SL() { // 算法2.15 // 若备用空间链表非空，则返回分配的结点下标，否则返回0 int i = space[0].cur; if (space[0].cur) space[0].cur = space[space[0].cur].cur; return i; } // Malloc_SL void Free_SL(int k) { // 算法2.16 // 将下标为k的空闲结点回收到备用链表 space[k].cur = space[0].cur; space[0].cur = k; } // Free_SL void Insert_SL(SLinkList& S, int i, ElemType e){ // 往静态链表S中的第 i 个位置前插入e int cur = S.elem; // 指向静态链表中的第一个节点 int j=0; int newNodeIndex; // 存储新分配的节点下标 while(j < i-1){ // 寻找第 i-1 个节点 cur = space[cur].cur; ++j; } newNodeIndex = Malloc_SL(); // 分配新的节点 strcpy(space[newNodeIndex].data,e); // 在新的节点中存入数据 space[newNodeIndex].cur = 0; // 指针为空，这一点很重要 space[newNodeIndex].cur = space[cur].cur; // 插入静态链表中 space[cur].cur = newNodeIndex; S.length++; // 插入后静态链表长度加1 } void Delete_SL(SLinkList& S, int i){ // 删除静态链表中的第 i 个节点 int cur = S.elem; // 指向静态链表中的第一个节点 int j=0; int delCur; // 存储待删除节点的下标 while(j < i-1){ // 寻找第 i-1 个节点 cur = space[cur].cur; ++j; } delCur = space[cur].cur; // 找到待删除节点的下标 space[cur].cur = space[delCur].cur; // 删除节点 Free_SL(delCur); // 释放节点 S.length--; // 删除后静态链表长度减1 } void CreateList_SL(SLinkList& S){ // 创建静态链表 S.elem = Malloc_SL(); // 分配头结点的指针 space[S.elem].cur = 0; S.length = 0; S.listSize = 9; } void Show_space(){ // 将静态链表中所有的节点显示出来 int i; for(i=0;i<MAXSIZE;i++){ printf("%-8s%2d\n", space[i].data, space[i].cur); } } int main(){ SLinkList S; // 定义静态链表 char str[10]; // 用来获得指令 int a; // 存储位置 ElemType e; // 存储元素 InitSpace_SL(); // 初始化备用链表 CreateList_SL(S); // 创建静态链表 while(scanf("%s", str) != EOF){ if(strcmp(str, "insert") == 0){ // 插入元素 scanf("%d%s", &a, e); Insert_SL(S, a, e); }else if(strcmp(str, "delete") == 0){ // 删除元素 scanf("%d", &a); Delete_SL(S, a); }else if(strcmp(str, "search") == 0){ // 搜索元素 scanf("%s", e); printf("%2d\n********************\n", LocateElem_SL(S, e)); }else if(strcmp(str, "show") == 0){ // 显示静态链表状态 Show_space(); puts("********************"); // 注意空一行 } } return 0; }Java :
import java.util.*; class SNode { public String data; int next; SNode(int i,String u){next=i;data=u;} }; class StaticList { SNode List[]; int length,maxlen; StaticList(int n,String u) { length=0; maxlen=n; List=new SNode[n]; for(int i=0;i<n;i++) { List[i]=new SNode(i+1,u); } List[0].next=2; List[1].next=0; List[n-1].next=0; } void DestroyList() { length = 0; } void ClearList() { length=0; for(int i=0;i<maxlen;i++) { List[i].next=i+1; } List[0].next=2; List[1].next=0; List[maxlen-1].next=0; } boolean ListEmpty() { return (length == 0); } int ListLength() { return length; } String GetElem(int p) { int i=List[1].next,po; if(p<1||i==0||p>length+1) return null; else { po=1; while(p>1) { po=List[po].next; p--; } p=List[po].next; return List[p].data; } } int LocateElem(String e) { int i=List[1].next,po; if(i==0) return 0; else { po=1; while(po!=0) { po=List[po].next; if(e.compareTo(List[po].data)==0) return po; } } return 0; } boolean Insert(int p,String e) { int i=List[0].next,po; if(i==0||p>length+1) return false; else { po=1; while(p>1) { po=List[po].next; p--; } List[i].data=e; List[0].next=List[i].next; List[i].next=List[po].next; List[po].next=i; length++; return true; } } String Delete(int p) { int i=List[1].next,po; if(p<1||i==0||p>length+1) return null; else { po=1; while(p>1) { po=List[po].next; p--; } p=List[po].next; List[po].next=List[p].next; List[p].next=List[0].next; List[0].next=p; length--; return List[po].data; } } void ShowFrom() { for(int i=0;i<maxlen;i++) { System.out.printf("%-8S%2d\n",List[i].data,List[i].next); } } }; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); String t; int n; StaticList L=new StaticList(11,""); while(cin.hasNext()) { t=cin.next(); if(t.charAt(2)=='s') { n=cin.nextInt(); t=cin.next(); L.Insert(n, t); } else if(t.charAt(2)=='l') { n=cin.nextInt(); L.Delete(n); } else if(t.charAt(2)=='a') { t=cin.next(); System.out.printf("%2d\n",L.LocateElem(t)); System.out.println("********************"); } else { L.ShowFrom(); System.out.println("********************"); } } cin.close(); } }
admin
SU
@ 2024-12-10 22:03:04
- 1